心急的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

样例输出

一开始我以为只要将长度和重量升序，然后找出当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；

 #include<stdio.h>/*WA*/

 typedef struct

 {

     int length;

     int weight;

 }stick;

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int n,i,j,count=,first=;

         scanf("%d",&n);

         stick a[n],t;

         for(i=;i<n;i++)

             scanf("%d%d",&a[i].length,&a[i].weight);

         for(i=;i<n-;i++)

             for(j=i+;j<n;j++)

             {

                 if(a[i].length>a[j].length)

                 {

                     t=a[i];

                     a[i]=a[j];

                     a[j]=t;

                 }

             }

         for(i=;i<n-;i++)

             for(j=i+;j<n;j++)

             {

                 if((a[i].length==a[j].length)&&(a[i].weight>a[j].weight))

                 {

                     t=a[i];

                     a[i]=a[j];

                     a[j]=t;

                 }

             }

     for(i=;i<n;i++)

         printf("%d %d\n",a[i].length,a[i].weight);

     for(i=;i<n;i++)

     {

         if((a[i].length!=a[i-].length)&&(a[i].weight<a[i-].weight))

             count++;

     }

     if(first==)

       {

           printf("%d\n",count+);

          first=;

       }

     else

          printf("%d\n",count);

      }

 }

 #include<stdio.h>/*AC*/

 #include<algorithm>

 #include<string.h>/*memset函数将数组重置 memset（数组名，替换后元素，大小）*///大小一般为sizeof(数组名)（全部置换），sizeof（int）*n

 using namespace std;

 typedef struct

 {

     int length;

     int weight;

 }stick;

 bool cmp(stick x,stick y)/*sort排序方式*/

 {

     if(x.length<y.length)

         return true;

     if(x.length==y.length&&x.weight<y.weight)

         return true;

     return false;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         int count=,i,j,n,t;

         scanf("%d",&n);

         stick a[n];

         memset(a,,sizeof(a));

         for(i=;i<n;i++)

             scanf("%d%d",&a[i].length,&a[i].weight);

         sort(a,a+n,cmp);

         for(i=;i<n;i++)/*第一个木棒所需时间就是机器打开时间*/

         {

             if(a[i].weight!=)/*贪心策略，每次尽量多的加工木棒！！*/

             {

                 t=a[i].weight;

                 count++;

                 for(j=i+;j<n;j++)

                 {

                     if(a[j].weight>=t)

                     {

                         t=a[j].weight;

                         a[j].weight=;/*加工后的木棒质量置零*/

                     }

                 }

             }

         }

         printf("%d\n",count);

     }

 }

巴特西

心急的C小加

最新文章

热门文章