Problem Description
There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
(a) The setup time for the first wooden stick is 1 minute. (b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if ll) return 1;
     else if(a->l < b->l) return -1;
     else return a->w > b->w ? 1 : -1;
 }
 int main()
 {
     int t,n,cnt,cl,cw;
     int i,j;
     scanf("%d",&t);
     while(t--)
     {
         memset(sticks,0,sizeof(sticks));
         scanf("%d",&n);
         for( i = 0; i < n; i++)
             scanf("%d %d",&sticks[i].l,&sticks[i].w);
         qsort(sticks,n,sizeof(sticks[0]),cmp);
         sticks[0].flag = 1;
         cl = sticks[0].l;
         cw = sticks[0].w;
         cnt = 1;
         for( j = 1; j < n; j++)
         {
             for( i = j; i < n; i++)
             {
                 if(!sticks[i].flag&&sticks[i].l>=cl&&sticks[i].w>=cw)
                 {
                     cl = sticks[i].l;
                     cw = sticks[i].w;
                     sticks[i].flag = 1;
                 }
             }
             i = 1;
             while(sticks[i].flag)
                i++;
             j = i;
             if(j == n) break;
             cl = sticks[j].l;
             cw = sticks[j].w;
             sticks[j].flag = 1;
             cnt++;
         }
         printf("%dn",cnt);

     }
     return 0;
 }

您可能感兴趣的文章: