我大概写了个假算法? 快读+吸氧才从60分涨到90分。 T一个560ms/500ms 一直想在递归里把输赢结果赋上,但没成功。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
int N,R,Q;
int a,b;
typedef struct {
int a,b,id;
//number,score,strength;
}Node;
Node p[400010]={{0,0}};
Node temp[400010]={{0,0}};
bool cmp(Node a,Node b){
// return a.a>b.a || (a.a==b.a && a.id < b.id);
if(a.a==b.a)
return a.id < b.id;
return a.a>b.a;
}
inline int read(){//快读
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void mergesort(int l,int r){
if(l==r) return;
int mid=(l+r)/2;
int i=l;
int k=l;
int j=mid+1;
mergesort(l ,mid);
mergesort(mid+1,r );
while(i<=mid && j<=r){
if(cmp(p[i],p[j])) temp[k++]=p[i++];
else temp[k++]=p[j++];
}
while(i<=mid) temp[k++]=p[i++];
while(j<=r) temp[k++]=p[j++];
for(i=l;i<=r;i++) p[i]=temp[i];
}
void print(){
cout << R << ":";
for(int i=1;i<=N;i++){
printf("%d ",p[i].id);
}
cout << "\n";
}
int main() {
cin >> N >> R >> Q;
N*=2;
for(int i=1;i<=N;i++){
p[i].a=read();
p[i].id=i;
}
for(int i=1;i<=N;i++){
p[i].b=read();
}
stable_sort(p+1,p+N+1,cmp);
while(R--) {
for(int i=1;i<N;i+=2){
if(p[i].b > p[i+1].b) p[i].a++;
if(p[i].b < p[i+1].b) p[i+1].a++;
if(cmp(p[i+1],p[i])){
swap(p[i],p[i+1]);
}
}
mergesort(1,N);
}
stable_sort(p+1,p+N+1,cmp);
cout << p[Q].id;
}