每次都搞快排，看数据，应该过不了。
如果对归并排序不陌生，那这道题应该没啥问题。第一次排序后，对每轮比赛中输和赢的分成两个序列，这两个序列必然有序，归并一次就够了。时间复杂度：nlogn+r*n。
代码：
#include<fstream>
#include<algorithm>
using namespace std;
const long N(200001);
struct node
{
long No,shili,score;
};
node a[N],b[N],c[N];
long n,r,q;
bool comp(const node &x,const node &y)
{
if (x.score!=y.score) return (x.score>y.score);
return (x.No<y.No);
}
void deal()
{
long i,j,k,j1,k1;
for (i=0;i<n;i++)
if (a[2*i].shili>a[2*i+1].shili)
a[2*i].score++,b[i]=a[2*i],c[i]=a[2*i+1];
else a[2*i+1].score++,b[i]=a[2*i+1],c[i]=a[2*i];
for (i=j=k=0;j<n&&k<n;i++)
a[i]=(comp(b[j],c[k])?b[j++]:c[k++]);
while (j<n) a[i++]=b[j++];
while (k<n) a[i++]=c[k++];
}
int main()
{
ifstream cin("swiss.in");
ofstream cout("swiss.out");
cin>>n>>r>>q;
for (long i=0;i<n+n;i++) { cin>>a[i].score; a[i].No=i+1; }
for (long i=0;i<n+n;i++) cin>>a[i].shili;
sort(a,a+2*n,comp);
for (long i=0;i<r;i++) deal();
cout<<a[q-1].No<<endl;
return 0;
}
posted on 2012-06-05 23:00
龙在江湖 阅读(891)
评论(0) 编辑 收藏 引用 所属分类:
竞赛题解_NOIP