hdu 1051 Wooden Sticks

这个题直接用贪心做。
题意就是一个机器重置一次要一分钟，只要长度和重量都比前一次小则不用重置机器，可以直接加工。求重置最少的次数。

首先对它排序，然后一个一个找满足条件的，并标记这个已经被加工了，被加工的不需要在加工。

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

struct Node
{
    int w,l;
    int y;   //标记
} a[5010];

bool cmp(Node a, Node b)
{
    if(a.l == b.l)
        return a.w > b.w;
    return a.l > b.l;
}

int main()
{
    int t,n,i,j,p,weight;
    scanf("%d",&t);
    while(t--)
    {
        p = 0;
        scanf("%d",&n);
        for(i = 0; i < n; i++)
        {
            scanf("%d%d",&a[i].l,&a[i].w);
            a[i].y = 1;
        }
        sort(a,a+n,cmp);
        for(i = 0; i < n; i++)
        {
            if(a[i].y == 1)   //如果这个没有被用过，则时间加一
            {
                a[i].y = 0;   //标记这个已经用了
                p++;          //时间加一
                weight = a[i].w; //更新最大重量
                for(j = i+1; j < n; j++)  //往后继续寻找
                {
                    if(a[j].w <= weight && a[j].y == 1)  //重量小于等于最大重量的并且没有被用过的则用
                    {
                        a[j].y = 0;
                        weight = a[j].w;    //更新重量
                    }
                }
            }
        }
        printf("%d\n",p);
    }

    return 0;
}

补充：软件开发 , C++ ,

上一个：UVa10878 - Decode the tape
下一个：将边权拆成两半加到它所关联的两个点的点权中即可