In a racing championship there are N racing drivers. The drivers are divided in K classes.
After a race, a driver is declared a winner if all the drivers that finish in front of him are from better classes (with smaller indices than his own).
As the main organiser of the championship, you can choose for each race which drivers are allowed to participate. Find the minimum number of races needed such that every driver is a winner at least once.
The first line contains 2 integers N and K.
Each of the next N lines contains 2 integers a_i and b_i. The first integer a_i?? represents the class of driver i, while b_i is his place in a race with all the N drivers.
Print the answer on the first line.
#include<bits/stdc++.h> using namespace std; #define MAXN 100000+10 struct per{int a,b;}p[MAXN]; int n,k,d[MAXN]; bool cmp(per x,per y){return x.b<y.b;} int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d%d",&p[i].a,&p[i].b); sort(p+1,p+n+1,cmp); d[1]=p[1].a; int len=1; for(int i=2;i<=n;i++){ if(d[len]>=p[i].a)d[++len]=p[i].a; else{ int l=1,r=len,mid,ans=-1; while(l<=r){ mid=(l+r)>>1; if(d[mid]<p[i].a){ ans=mid; r=mid-1; } else l=mid+1; } d[ans]=p[i].a; } } printf("%d\n",len); return 0; }
原文：http://www.cnblogs.com/NINGLONG/p/7606850.html