stick.cpp

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

//Korea 2001 ACM B stick;
//Li Rui,2001.11.12
//sort by one key and then greedy

#include<iostream.h>
#include<fstream.h>

typedef int line[5001];

line l,w,a;


main()
{
 ifstream cin("stick.in");
 ofstream cout("stick.out");

 int n;
 int i,j;
   cin>>n;
   for (i=1;i<=n;i++)
    cin>>l[i]>>w[i];
   for (i=1;i<n;i++)
    for (j=i+1;j<=n;j++)
     if (l[i]>l[j] || (l[i]==l[j] && w[i]>w[j]))
       {
         int temp;
         temp = l[i];
         l[i] = l[j];
         l[j] = temp;
         temp = w[i];
         w[i] = w[j];
         w[j] = temp;
       }

    for (i=1;i<=n;i++) a[i]=2000000000;

    int p=0,jj,up;
    for (i=n;i>0;i--)
     {
       jj=0; up = 2000000000;
       for (j=1;j<=p;j++)
        if (a[j]>=w[i] && a[j]<up)
         {
           up=a[j];
           jj=j;
         }
       if (jj==0) a[++p]=w[i];
       else a[jj]=w[i];
     }

     cout<<p<<endl;
     return 0;
}