Wooden Sticks

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <algorithm>       //sort函数所需头文件
 5 using namespace std;
 6 
 7 struct stick
 8 {
 9     int l,w;       //长度和重量
10     int v;        //用于标记木棒是否被处理
11 }s[5500];
12 
13 int cmp(const stick &a,const stick &b)
14 {
15     if(a.l==b.l)
16         return a.w<b.w;
17     return a.l<b.l;
18 }              //定义排序原则
19 
20 int main()
21 {
22     int i,t,k,n,cnt,ans;       //cnt表示被标记元素的个数（如果元素全部被标记cnt=n说明他们都找到了其升序子序列），ans为准备时间
23     scanf("%d",&t);
24     while(t--)
25     {
26         scanf("%d",&n);
27         for(i=0;i<n;i++)
28         {
29             scanf("%d%d",&s[i].l,&s[i].w);
30             s[i].v=0;     //初始标记为0
31         }
32         sort(s,s+n,cmp);
33         cnt=0;
34         k=0;
35         ans=0;
36         while(cnt!=n)
37         {
38             k=0;
39             while(k<n&&s[k].v==1)     //依次遍历到上次循环找到的升序子序列 直到不满足条件的第一个元素
40                 k++;
41             ans++;           //准备时间要+1
42             for(i=k;i<n;i++)           //找出一个从k开始的升序子序列 并标记为1
43             {
44                 if(s[i].v==0&&s[i].l>=s[k].l&&s[i].w>=s[k].w)   //之前找过的已经标记为1了，所以不可以再次使用
45                 {
46                     s[i].v=1;
47                     cnt++;    //记录标记元素的个数
48                     k=i;      //k指向当前处理的木棒
49                 }
50             }
51         }
52         printf("%d\n",ans);
53     }
54     return 0;
55 }