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;
}