题目链接：
http://codevs.cn/problem/4888/
https://www.luogu.org/problem/show?pid=2093
题目描述
某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若i<j，则Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组?
输入输出格式
输入格式：
第一行为一个整数N（N<=1000），表示零件的个数。第二行有N对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过10000。
输出格式：
仅一行，即最少分成的组数。
输入输出样例
输入样例#1：
5 8 4 3 8 2 3 9 7 3 5
输出样例#1：
2
分析：
可以考虑先按长度从小到大排序，长度相等者按重量从小到大排序。
然后第一个零件单独一个组。
从第二个零件开始处理所有零件的分组：
若是第i个零件的重量比某个已经存在的组（假设为第j组）的最大重量还要大，则第i个零件可以归入第j组。
假如第i个零件无法归入任何一个组，则第i个零件单独形成一个新的组（第k组）。
有可能第i个零件可以归入多个组（假设为j1、j2、j3、……、jn），从最优的角度来考虑，应该选择组内最重零件较大的那一个组。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int a[1100],b[1100]; 5 6 void qsort(int l,int r) 7 { 8 int i,j,mid,p; 9 i=l; j=r; 10 mid=a[(l+r)/2]; 11 while (i<=j) 12 { 13 while (a[i]<mid) i++; 14 while (a[j]>mid) j--; 15 if (i<=j) 16 { 17 p=a[i]; a[i]=a[j]; a[j]=p; 18 p=b[i]; b[i]=b[j]; b[j]=p; 19 i++; j--; 20 } 21 } 22 if (l<j) qsort(l,j); 23 if (i<r) qsort(i,r); 24 } 25 26 int main() 27 { 28 freopen( "stick.in" , "r" ,stdin); 29 freopen( "stick.out" , "w" ,stdout); 30 int n,i,k,x,j,c[1010]; 31 cin>>n; 32 for (i=1;i<=n;i++) 33 { 34 cin>>a[i]>>b[i]; 35 a[i]=a[i]*10000+b[i]; 36 } 37 qsort(1,n); 38 k=1; 39 c[1]=b[1]; 40 for (i=2;i<=n;i++) 41 { 42 x=0; 43 for (j=1;j<=k;j++) 44 if (c[j]<=b[i]) 45 { 46 if (x==0) x=j; 47 else 48 if (c[j]>c[x]) x=j; 49 } 50 if (x==0) c[++k]=b[i]; 51 else c[x]=b[i]; 52 } 53 cout<<k<<endl; 54 return 0; 55 }
