题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=25
题目大意：机器运送n个木条，每个木条有一个长度和重量。运送第一根木条需要1分钟的准备时间，接下来如果后一根木条的长度和重量都大于等于前一根木条，则不需要准备时间，否则需要1分钟的准备时间，求运完所有木条最少时间。 比如有5根木条，长度和重量分别是(4,9), (5,2), (2,1), (3,5), (1,4),则需要2分钟就可运完第1分钟运(1,4), (3,5), (4,9)；第2分钟运 (2,1), (5,2)
分析：快速排序加贪心。首先按照木条长度从小到大排，第二关键字是重量，这时在f[]中做贪心，若遇到比其中一个大的就直接在里面覆盖，否则计数器p++，并把该数压入f[]
比如(4,9), (5,2), (2,1), (3,5), (1,4),排序后是(1,4),(2,1),(3,5),(4,9), (5,2), 这样以后主关键字是从小到大排的不需要考虑。
每步调试之后是：f[1]=4; f[2]=1; f[1]=5; f[1]=9; f[2]=5; 表示第1分钟运(1,4), (3,5), (4,9)；第2分钟运 (2,1), (5,2)
代码如下：
1 # include<stdio.h> 2 # include<string.h> 3 # include<stdlib.h> 4 # define size 5001 5 6 struct node{ 7 int l,w; 8 }data[size]; 9 10 int f[size]; 11 12 int cmp(const void *a,const void *b){ 13 struct node *c = (node *)a; 14 struct node *d = (node *)b; 15 if(c->l == d->l) 16 return c->w - d->w; 17 return c->l - d->l; 18 } 19 20 int main(){ 21 int T; 22 int n,p,i,j,flag; 23 scanf("%d",&T); 24 while(T--){ 25 scanf("%d",&n); 26 for(i=0;i<n;i++) 27 scanf("%d%d",&data[i].l,&data[i].w); 28 qsort(data,n,sizeof(data[0]),cmp); 29 p =0 ; 30 memset(f,0,sizeof(f)); 31 for(i=0;i<n;i++){ 32 flag = 0; 33 //判断第i个数与f[]已存在的数的大小，若大则记录f[]中比它小的数的下标 34 for(j=1;j<=p;j++) 35 if(data[i].w >= f[j] && f[j] != 0){ 36 flag = j; 37 break; 38 } 39 //原有数中不存在比当前数小的，则压入 40 if(flag==0){ 41 p++; 42 f[p] = data[i].w; 43 } 44 //存在则用当前数覆盖原来的 45 else 46 f[flag] = data[i].w; 47 } 48 printf("%d ",p); 49 } 50 return 0; 51 }