poj1065

题目大意:

木棍(好吧,承认确实做过这个题,嘎嘎)
有一堆木棍大约有n根,木棍的长度和重量都预先知道,这些木棍会在一个木工机械上一个接一个的处理,这需要一些时间,称为设置时间,为机械准备处理一根木头,这个设置时间跟清洁还有机械的工具和形状的改变有关系,木工机床安装时间如下:
(a)第一根木棍的设置时间是1 minute.
(b)正确加工处理一个长l重w的木棍后,如果下一根木头的长 l <= l' and w <= w'则不需要花费时间,否则将要花费1minute的设置时间。你需要找出来最小的花费时间。
解析,好吧这个实在是没有什么创意啊,直接K掉吧
AC
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxn 5005
#define INF 0xffffff struct stick
{
    int l, w;
}a[maxn], b[maxn]; bool cmp(stick n1, stick n2)
{
    if(n1.w != n2.w)return n1.w < n2.w;
    return n1.l < n2.l;
}
int Find(int n, stick p)
{
    int i, k=-1, MinLen=INF;
    for(i=0; i<n; i++)
    {
        if(p.l >= b[i].l && MinLen > p.l-b[i].l)
            k=i, MinLen = p.l-b[i].l;
    }
    return k;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int i, n, k=0;
        scanf("%d",&n);
        for(i=0; i<n; i++)
            scanf("%d%d",&a[i].l,&a[i].w);         sort(a, a+n, cmp);         for(i=0; i<n; i++)
        {
            int ans =Find(k, a[i]);
            if(ans ==-1)
                ans = k++;
            b[ans]= a[i];
        }
        printf("%d\n", k);
    }
    return 0;

}

上一篇:Unity 3D 游戏上线之后的流水总结


下一篇:STL 内存释放