poj 1065 Wooden Sticks

思想很容易想到，证明是看了别的解题报告：利用到偏序定理：贪心算法实现

  #include <iostream>   



#include <algorithm>   
using namespace std;  
/*328K  16MS*/  
typedef struct _pair  
{  
        int l;  
        int w;  
}Pair;  
  
int cmp(const void *a,const void *b)  
{  
    Pair a1=*(Pair *)a;  
    Pair b1=*(Pair *)b;  
    if(a1.l==b1.l)  
       return a1.w-b1.w;  
    return a1.l-b1.l;  
}  
  
int main()  
{  
    int t;  
    cin>>t;  
    while(t--)  
    {  
        int n;  
        cin>>n;  
        Pair *p=new Pair[n];  
        bool *b=new bool[n];  
        memset(b,false,sizeof(bool)*n);  
  
        for(int i=0;i<n;i++)  
            cin>>p[i].l>>p[i].w;  
        //计算反链   
        qsort(p,n,sizeof(p[0]),cmp);  
        int count=0;   
        for(int i=0;i<n;i++)  
        {        
                if(b[i])    continue;  
                if(!b[i])    count++;  
                int k=i;  
                for(int j=i+1;j<n;j++)  
                {  
                   //具有可比的都加到一个集合里面   
                   if(p[j].w>=p[k].w&&!b[j])  
                      {  
                                 b[j]=true;  
                                 k=j;  
                      }      
                }  
                b[i]=true;  
        }  
          
        cout<<count<<endl;  
        delete []p;  
        delete []b;  
    }    
    system("pause");  
    return 0;  
}  

#include <iostream>
#include <algorithm>
using namespace std;
/*328K	16MS*/
typedef struct _pair
{
        int l;
        int w;
}Pair;

int cmp(const void *a,const void *b)
{
    Pair a1=*(Pair *)a;
    Pair b1=*(Pair *)b;
    if(a1.l==b1.l)
       return a1.w-b1.w;
    return a1.l-b1.l;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        Pair *p=new Pair[n];
        bool *b=new bool[n];
        memset(b,false,sizeof(bool)*n);

        for(int i=0;i<n;i++)
            cin>>p[i].l>>p[i].w;
        //计算反链
        qsort(p,n,sizeof(p[0]),cmp);
        int count=0; 
        for(int i=0;i<n;i++)
        {      
                if(b[i])    continue;
                if(!b[i])    count++;
                int k=i;
                for(int j=i+1;j<n;j++)
                {
                   //具有可比的都加到一个集合里面
                   if(p[j].w>=p[k].w&&!b[j])
                      {
                                 b[j]=true;
                                 k=j;
                      }    
                }
                b[i]=true;
        }
        
        cout<<count<<endl;
        delete []p;
        delete []b;
    }  
    system("pause");
    return 0;
}

补充：软件开发 , C++ ,

上一个：usaco 2011 Dec Gold(Grass Planting-树链剖分第一题)
下一个：字符串查找--B中是否有元素不在A中