题目描述
某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若i<j，则Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组?
输入输出格式
输入格式：
第一行为一个整数N（N<=1000），表示零件的个数。第二行有N对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过10000。
输出格式：
仅一行，即最少分成的组数。
输入输出样例
输入样例#1：
输出样例#1：
题解
毫无疑问，先把零件以长度为第一关键字，重量为第二关键字排序
之后顺序枚举零件，对每一根零件求和它重量最接近且尽量大的组塞进去
#include<cstdio>
#include<algorithm>
#define N 1001
using namespace std;
int n,pb[N];
struct stick{
int l,w;
bool operator<(const stick h)const{
if(l^h.l)return l<h.l;
return w<h.w;
}
}s[N];
inline void push(int x){
int p=;
for(int i=;i<=pb[];i++){
if((!p)&&x>=pb[i])
p=i;
else
if(x>=pb[i]&&pb[p]<pb[i])
p=i;
}
p?pb[p]=x:
pb[++pb[]]=x;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&s[i].l,&s[i].w);
sort(s+,s++n);
pb[++pb[]]=s[].w;
for(int i=;i<=n;i++)
push(s[i].w);
printf("%d\n",pb[]);
return ;
}