题目链接：https://www.luogu.com.cn/problem/P1309
如果是新手可能马上会想到sort排序，每比一次就排一次，但是这样的时间复杂度有点高，只有60分；
这是因为每次比完赛会产生两个有序数列（输/赢），只需要把这两个有序数列合并成一个有序数列，而sort则是排了所有的数，显然浪费了时间
一提到有序数列，会想到归并排序——由于两个有序数列是现成的，所以只要并就行了，省了不少时间，可以AC
上代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,r,q;
4 int a[200100],s[200100],w[200100],win[200100],lose[200100];//a——序号，s——分数，w——战力
5 bool cmp(int a,int b){//排序的时候判断大小（用标号）
6 if(s[a]==s[b]){
7 return a<b;
8 }
9 return s[a]>s[b];
10 }
11 void Q(){//归并排序——并
12 int i,j;
13 i=j=1,a[0]=0;
14 while(i<=win[0]&&j<=lose[0]){//输赢两个有序序列，所以直接并
15 if(cmp(win[i],lose[j]))
16 a[++a[0]]=win[i++];//回到a（序号）数组
17 else
18 a[++a[0]]=lose[j++];
19 }
20 while(i<=win[0])a[++a[0]]=win[i++];
21 while(j<=lose[0])a[++a[0]]=lose[j++];//处理掉剩余的数
22 }
23 int main(){
24 cin>>n>>r>>q;
25 n*=2;
26 for(int i=1;i<=n;i++){
27 cin>>s[i];
28 }
29 for(int i=1;i<=n;i++){
30 cin>>w[i];
31 a[i]=i;
32 }
33 sort(a+1,a+n+1,cmp);//先快排一次
34 for(int i=1;i<=r;i++){
35 win[0]=lose[0]=0;//0的正好没用，用来计数
36 for(int j=1;j<=n;j+=2){
37 if(w[a[j]]>w[a[j+1]]){//判断哪方胜利
38 s[a[j]]++;
39 win[++win[0]]=a[j];
40 lose[++lose[0]]=a[j+1];//加入
41 }
42 else{
43 s[a[j+1]]++;
44 win[++win[0]]=a[j+1];
45 lose[++lose[0]]=a[j];
46 }
47 }
48 Q();
49 }
50 cout<<a[q];//结束
51 return 0;
52 }
标签：
留言评论