1 #include <stdio.h> 2 #include <stdlib.h> 3  4 typedef struct stick{/*其中l为length， w为weight，visit为标记当前组是否已被排列出来*/ 5     int l, w; 6     int visit; 7 }stick; 8 int cmp(const void *a, const void *b)//定义比较函数 9 {10     stick *c = (stick *)a;11     stick *d = (stick *)b;12     if(c -> w == d -> w)13     {14         return c ->l - d -> l;//从小到大排列， 先按重量的大小排，如果重量相同的时候， 在按照长度来排15     }16     return c -> w - d -> w;17 }18 int main()19 {20 //    freopen("1.txt", "r", stdin);21 //    freopen("2.txt", "w", stdout);22     int t;23     scanf("%d", &t);24     while(t --)25     {26         int n, cnt = 0, len;//len用来保存下面的临时长度，cnt计数， 一共花费多少分钟27         stick arr[5010];28         scanf("%d", &n);29         for(int i = 0; i < n; i++)30         {31             scanf("%d%d", &arr[i].l, &arr[i].w);32             arr[i].visit = 1;//初始化为133         }34         qsort(arr, n, sizeof(stick), cmp);//排序， 当然也可以用sort排序35         for(int i = 0; i < n; i++)36         {37             if(arr[i].visit)//如果当前没有被排列出来，就再来一列进行排列38             {39                 len = arr[i].l;/*保存当前的长度，因为是按照重量来排列的，所以重量一定是递增的，即后一个肯定大于等于前一个，所以不必再比较重量*/40                 for(int j = i + 1; j < n; j++)41                 {42                     if(arr[j].visit && len <= arr[j].l)//如果满足要求，一直找下去43                     {44                         arr[j].visit = 0;//找到后标记为零，这样下次就不会从另一列中再找它了45                         len = arr[j].l;46                     }47                 }48                 cnt++;49             }50         }51         printf("%d\n", cnt);52     }53     return 0;54 }