心急的C小加

描述: C小加有一些木棒，它们的长度和质量都已经知道，需要一个机器处理这些木棒，机器开启的时候需要耗费一个单位的时间，如果第i+1个木棒的重量和长度都大于等于第i个处理的木棒，那么将不会耗费时间，否则需要消耗一个单位的时间。因为急着去约会，C小加想在最短的时间内把木棒处理完，你能告诉他应该怎样做吗？

输入

第一行是一个整数T(1<T<1500)，表示输入数据一共有T组。
每组测试数据的第一行是一个整数N（1<=N<=5000）,表示有N个木棒。接下来的一行分别输入N个木棒的L，W（0 < L ,W <= 10000），用一个空格隔开，分别表示木棒的长度和质量。

输出

处理这些木棒的最短时间。

样例输入

3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

样例输出

2
1
3

一开始我以为只要将长度和重量升序，然后找出当length[i]!=length[i-1]时，weight[i]<weight[i-1]然后count++，结果发现不是这样，1 4 2 1 3 5 4 9 5 2这样那就count为3
实际上顺序为1 4 3 5 4 9 2 1 5 2 属于贪心策略，尽量让每次加工的木棒多；这道题对时间有很高要求，选择排序不可行，选择快排sort；

 1 #include<stdio.h>/*WA*/
 2 typedef struct 
 3 {
 4     int length;
 5     int weight;
 6 }stick;
 7 int main()
 8 {
 9     int t;
10     scanf("%d",&t);
11     while(t--)
12     {
13         int n,i,j,count=0,first=1;
14         scanf("%d",&n);
15         stick a[n],t;
16         for(i=0;i<n;i++)
17             scanf("%d%d",&a[i].length,&a[i].weight);
18         for(i=0;i<n-1;i++)
19             for(j=i+1;j<n;j++)
20             {
21                 if(a[i].length>a[j].length)
22                 {
23                     t=a[i];
24                     a[i]=a[j];
25                     a[j]=t;
26                 }
27             }
28         for(i=0;i<n-1;i++)
29             for(j=i+1;j<n;j++)
30             {
31                 if((a[i].length==a[j].length)&&(a[i].weight>a[j].weight))
32                 {
33                     t=a[i];
34                     a[i]=a[j];
35                     a[j]=t;
36                 }
37             
38             }
39     for(i=0;i<n;i++)
40         printf("%d %d
",a[i].length,a[i].weight);
41     for(i=1;i<n;i++)
42     {
43         if((a[i].length!=a[i-1].length)&&(a[i].weight<a[i-1].weight))
44             count++;
45     }
46     if(first==1)
47       {
48           printf("%d
",count+1);
49          first=0;
50       }
51     else
52          printf("%d
",count);
53      }
54 }

 1 #include<stdio.h>/*AC*/
 2 #include<algorithm>
 3 #include<string.h>/*memset函数将数组重置 memset（数组名，替换后元素，大小）*///大小一般为sizeof(数组名)（全部置换），sizeof（int）*n
 4 using namespace std;
 5 typedef struct 
 6 {
 7     int length;
 8     int weight;
 9 }stick;
10 bool cmp(stick x,stick y)/*sort排序方式*/
11 {
12     if(x.length<y.length)
13         return true;
14     if(x.length==y.length&&x.weight<y.weight)
15         return true;
16     return false;
17 }
18 int main()
19 {
20     int T;
21     scanf("%d",&T);
22     while(T--)
23     {
24         int count=0,i,j,n,t;
25         scanf("%d",&n);
26         stick a[n];
27         memset(a,0,sizeof(a));
28         for(i=0;i<n;i++)
29             scanf("%d%d",&a[i].length,&a[i].weight);
30         sort(a,a+n,cmp);
31         for(i=0;i<n;i++)/*第一个木棒所需时间就是机器打开时间*/
32         {
33             if(a[i].weight!=0)/*贪心策略，每次尽量多的加工木棒！！*/
34             {
35                 t=a[i].weight;
36                 count++;
37                 for(j=i+1;j<n;j++)
38                 {
39                     if(a[j].weight>=t)
40                     {
41                         t=a[j].weight;
42                         a[j].weight=0;/*加工后的木棒质量置零*/
43                     }
44                 }
45             
46             }
47 
48         }
49         printf("%d
",count);
50     }
51 }