题解 P2093 【零件分组】

Timothy · 2015-07-21 22:52:23 · 题解

【题目大意】

某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若i<j，则Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组?

【算法分析】

这道题采用贪心的解法，先把零件的长度从小到大排序，如果长度相同则按重量从小到大排序。那么此时只要考虑重量是否为升序即可（类似于导弹拦截的第二问）。Sum[i]表示第i组最后一个零件的重量。每一个零件都搜索一遍sum[]，找一个重量小于该零件且重量最大的组别，把零件放入该组，若找不到这样的组，则增加一组。

得分：100

时间复杂度：O(nlogn+n)

空间复杂度：O(N)

【C++代码】
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,sum[1001],ans;
bool flag;
struct node
{
    int l,w;
}a[1001];
bool cmp(node i,node j){return i.l==j.l?(i.w<j.w):(i.l<j.l);}
int main ()
{
    scanf ("%d",&n);
    for (int b=1;b<=n;++b)scanf ("%d%d",&a[b].l,&a[b].w);
    sort(a+1,a+n+1,cmp);
    sum[1]=a[1].l;ans=1;
    for (int b1=2;b1<=n;++b1)
    {
        flag=false;
        int wz,cd;
        for (int b=1;b<=ans;++b)
            if (sum[b]<=a[b1].w)
                if (!flag){flag=true;wz=b;cd=sum[b];}
                else if (sum[b]>cd){wz=b;cd=sum[b];}
        if (flag)sum[wz]=a[b1].w;
        else sum[++ans]=a[b1].w;
    }
    printf ("%d",ans);
    return 0;
}