【宁波市第23届中小学生计算机程序设计竞赛（初中组）T3】马（排序，最长不下降子序列）

 1 #include <algorithm>
 2 #include <cstdio>
 3  
 4 struct fighters{
 5     float h,f;
 6 }a[9001];
 7  
 8 int n,ans,tot=1;
 9 float maxn,f[9001];
10 #define max(x,y) (x>y?x:y)
11  
12 bool cmp(fighters x,fighters y){
13     if(x.h==y.h)return x.f<y.f;
14     return x.h<y.h;
15 }
16  
17 int main(void){
18     scanf("%d",&n);
19     for(int i=1;i<=n;++i)
20         scanf("%f",&a[i].h);
21     for(int i=1;i<=n;++i)
22         scanf("%f",&a[i].f);
23     std::sort(a+1,a+n+1,cmp);
24     for(int i=1;i<n;++i)
25         if((a[i].f==a[i+1].f)&&(a[i].h==a[i+1].h))
26             a[i].f=10;
27     std::sort(a+1,a+n+1,cmp);
28     f[1]=a[1].f;
29     for(int i=2;i<=n;++i){
30         if(a[i].f>=f[tot]){
31             f[++tot]=a[i].f;
32             continue;
33         }
34         int j=std::upper_bound(f+1,f+tot+1,a[i].f)-f;
35         f[j]=a[i].f;
36     }
37     printf("%d",tot);
38 }