1270: Wooden Sticks [贪心]_综合

点击打开链接

1270: Wooden Sticks [贪心]

时间限制: 1 Sec 内存限制: 128 MB

提交: 31 解决: 11 统计

题目描述

Lialosiu要制作木棍，给n根作为原料的木棍的长度和重量。根据要求求出制作木棍的最短时间。

首先我们知道制作第一个木棍需要1分钟，若是接着要制作的木棍的重量和长度都不少于当前的木棍，那么就不需要建立的时间，若是没有，则再需要建立时间，也就是1分钟。

举个例子，如果你有五个原料木棍，他们的长度和重量分别是(4,9), (5,2), (2,1), (3,5), 和 (1,4), 那么第一分钟你要建立一根木棍作为起始参照，比如(1,4)接下来(3,5)和(4,9)都可以不花费时间，然后用第二分钟选取(2,1)这跟木棍作为参照，接下来(5,2)可以不花费任何时间，总的来说，你一共花费了两分钟，这也是你可能使用的最少时间。

现在给了n个木棍的长度和重量，你能求出使用这些木棍的最少时间吗？

输入

首先，输入一个正整数T ,代表有T组数据。

接下来，第二行你要输入正整数n（1<=n<=5000）代表的你的原料木棍个数。

第三行你要输入2*n 个正整数l1, w1, l2, w2, ..., ln, wn，每一个数字都不超过10000 。 li代表第i根木棍的长度，wi代表第i根木棍的重量。

输出

输出一个整数，代表最少需要的时间t。

样例输入

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

来源

代码实现：(AC代码)

[cpp]  view plain copy 
      
     
 #include <iostream>  
 #include <string.h>  
 #include <algorithm>  
 using namespace std;  
 struct w  
 {  
     int l,w;  
     bool ok;//用来标记是否木头被处理掉。  
 }wood[5003];  
 bool cmp(w a,w b)//首先按长度从大到下排序，长度相同的按重量从大到小排序  
 {  
     if(a.l>b.l)  
         return true;  
     else if(a.l==b.l)  
     {  
         if(a.w>b.w)  
             return true;  
         return false;  
     }  
     return false;  
 }  
 int main()  
 {  
     int t;cin>>t;  
     while(t--)  
     {  
         int n;cin>>n;  
         for(int i=1;i<=n;i++)  
             {  
                 cin>>wood[i].l>>wood[i].w;  
                 wood[i].ok=0;//初始化木头都未处理。  
             }  
         sort(wood+1,wood+1+n,cmp);//排序。  
         int setup=0;int emp=0;//已经被处理的木头的个数  
         w temp;  
         while(1)  
         {  
             if(emp==n)//当所有的木头都被处理时，结束循环  
                 break;  
             for(int i=1;i<=n;i++)//寻找每次机器启动，处理的那根长度最长，重量最重的那根木头。实质，多次寻找最长递减子序列，及寻找最大的那个元素  
             {  
                 if(!wood[i].ok)  
                     {  
                         temp=wood[i];  
                          break;//别忘了这一句  
                     }  
             }  
            // cout<<"**"<<temp.l<<" "<<temp.w<<endl;  
             for(int i=1;i<=n;i++)  
             {  
                 if(!wood[i].ok&&wood[i].l<=temp.l&&wood[i].w<=temp.w)//前提是该木头没有被处理，所以必须加上！wood[i].ok  
                 {  
                     wood[i].ok=1;//该木头被处理  
                     emp++;  
                     temp=wood[i];//及时更换长度最长，重量最重的那根木头，及递减子序列的当前元素的下一个元素。  
                 }  
             }  
             setup++;//一次启动处理结束。  
         }  
         cout<<setup<<endl;  
     }  
     return 0;  
 }  

[cpp]  view plain copy 
      
     
 print ? 
    
 #include<iostream>  
 #include<algorithm>  
 #include<cstring>  
   
 using namespace std;  
 struct node{  
     int l,w;  
 }p[10005];  
   
 int cmp(node a,node b)  
 {  
     if(a.l==b.l)  
     return a.w<b.w;   
       
     return a.l<b.l;  
 }  
   
 int main()  
 {  
     int t,n,i,j,k,v[10005],flag;  
     cin>>t;  
     while(t--)  
     {  
         long long sum=0;  
         cin>>n;  
         for(i=0;i<n;i++)  
         cin>>p[i].l>>p[i].w;  
           
         memset(v,0,sizeof(v));  
         sort(p,p+n,cmp);  
         v[0]=1;k=0;  
           
         while(k<n)  
         {  
             ++sum;  
             for(i=k+1,j=k,flag=1;i<n;++i)  
             {  
                 if(v[i])  
                 continue;  
                   
                 if((p[j].w<=p[i].w)&&(p[j].l<=p[i].l))  
                 {  
                     v[i]=1;  
                     j=i;  
                 }  
                 else  
                 {  
                     if(flag)  
                     {  
                         flag=0;  
                         k=i;  
                     }  
                 }  
             }  
             if(flag)  
             break;  
         }  
         cout<<sum<<endl;  
     }  
     return 0;  
 }  

刚开始想的是把长度和重量合成一个整数，然后进行排序，然后再把那个数%10，求出个位数字，但是这样想的话只是把重量当成个位数来处理，可以。如果是十位数字以上就不行了