首页 > ACM题库 > HDU-杭电 > HDU 1051 Wooden Sticks-贪心-[解题报告] C++
2013
11-26

HDU 1051 Wooden Sticks-贪心-[解题报告] C++

Wooden Sticks

问题描述 :

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l’ and weight w’ if l<=l’ and w<=w’. Otherwise, it will need 1 minute for setup.

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

输入:

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains n 2 positive integers l1, w1, l2, w2, …, ln, wn, each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

输出:

The output should contain the minimum setup time in minutes, one per line.

样例输入:

3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

样例输出:

2
1
3

2011-12-19 02:42:34

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1051

题意:有n个木棍长为l重为w。机器处理木棍,若前一根的l和w均不小于后一根,则不需要额外时间,否则需要额外时间1。问最小需要多少时间。

mark:网上说是贪心,想了很久想不明白,画了一下sample1的图(l当做x,w当做y描点),恍然大悟。

把所有元素按l从大到小排序后,其实就是导弹拦截系统的问题,求一个LIS(关于最少导弹拦截数等于最长非降子序列长度的证明,因为之前和其他同学讨论过,所以知道挺麻烦的。讨论了两天才勉强证出来,还很不简洁,不过这个结论还是对的)。这里数据是5000,所以要用O(nlgn)的方法。O(n^2)理论会超时,不过实际上跑62ms,还好。

代码:

# include <stdio.h>
# include <stdlib.h>


typedef struct node{
    int l, w ;
}node ;


node a[5010] ;
int dp[5010] ;


int cmp(const void *a, const void *b)
{
    node *p = (node*)a, *q = (node*)b ;
    if (p->l != q->l) return q->l - p->l ;
    return q->w - p->w ;
}


int main ()
{
    int T, n, i, j, ans ;
    scanf ("%d", &T) ;
    while (T--)
    {
        scanf ("%d", &n) ;
        for (i = 0 ; i < n ; i++)
            scanf ("%d%d", &a[i].l, &a[i].w) ;
        qsort(a, n, sizeof(node), cmp) ;
        ans = -1, dp[0] = 1 ;
        for (i = 1 ; i < n ; i++)
        {
            dp[i] = 1 ;
            for (j = 0 ; j < i ; j++)
            {
                if (a[j].w < a[i].w && dp[j]+1 > dp[i])
                    dp[i] = dp[j] + 1 ;
            }
            if (dp[i] > ans) ans = dp[i] ;
        }
        printf ("%d\n", ans) ;
    }
    return 0 ;
}


  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  3. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  4. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?