luoguP3034 [USACO11DEC]牛摄影Cow Photography

题目

---

考虑对于任意两头牛a和b，假设a在b前面。

他们在5张照片中，至少有3张照片，a在b前面，剩下一张可能是a移到了后面，还有一张可能是b移到了前面，但无论如何，至少有3张照片他们的相对位置保持不变。

这样就可以排序了。

p.s.还需要离散化。

code

#include<bits/stdc++.h>
#define N 20010
#define fsb(a,b,c) for(int a=b;a<=(c);a++)
#define fbs(a,b,c) for(int a=b;a>=(c);a--)
using namespace std;
int a[10][N],n,rk[N],b[N],x;
template<typename qw>inline void rll(qw &x){
 x=0;qw f=1;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
inline int cmp(int a,int b){
 return a<b;
}
inline int getrk(int x){
 int l=1,r=n,m;
 while(l+5<r){
  m=(l+r)>>1;
  if(rk[m]==x)return m;
  if(rk[m]<x)l=m;else r=m;
 }
 fsb(i,l,r)if(rk[i]==x)return i;
}
inline int cmp2(int aa,int bb){
 int rka=getrk(aa),rkb=getrk(bb);
 int cnt=0;
 fsb(i,1,5)cnt+=a[i][rka]<a[i][rkb]?1:0;
 return cnt>=3;
}
int main(){//a[i][j]表示在第i张图中，rk=j的位置 
 rll(n);
 fsb(i,1,n)rll(rk[i]),b[i]=rk[i];
 sort(rk+1,rk+1+n,cmp); 
// fsb(i,1,n)printf("%10d\n",rk[i]);
 fsb(i,1,n)a[1][getrk(b[i])]=i;
 fsb(j,2,5)
  fsb(i,1,n){
   rll(x);a[j][getrk(x)]=i; 
  }
// fsb(i,1,n)printf("%10d\n",a[2][i]);
 sort(b+1,b+1+n,cmp2);
 fsb(i,1,n)printf("%d\n",b[i]);
 return 0;
}