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;
}