poj 1065 Wooden Sticks_贪心

题意：将木棍放在机器里处理，第一根需要一分钟，剩余的如果大于等于前边放入的长度和重量，就不用费时间，否则需要一分钟，计算给出一组数的最少时间。

思路：先按长度排序，相同在比较重量，然后按顺序比较得出结果

#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=5010;
struct stick
{
    int length;
    int weight;
    bool vis;
}s[maxn];
bool cmp(stick s1,stick s2)
{
    if(s1.length<s2.length)
        return 1;
    else if(s1.length==s2.length)
        return s1.weight<s2.weight;
    return 0;
}

int main()
{
    int test,i,j,ans,n;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&s[i].length,&s[i].weight);
            s[i].vis=0;
        }
        sort(s,s+n,cmp);
        ans=0;
        for(i=0;i<n;i++)
        {
            if(!s[i].vis)
            {
                s[i].vis=true;
                ans++;
                int weight=s[i].weight;
                for(j=i+1;j<n;j++)
                {
                    if(!s[j].vis&&s[j].weight>=weight)
                    {
                        s[j].vis=1;
                        weight=s[j].weight;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

poj 1065 Wooden Sticks_贪心,布布扣,bubuko.com

poj 1065 Wooden Sticks_贪心

原文：http://blog.csdn.net/neng18/article/details/20577013