我把每个人的实力放在结构体里面发现答案会错,但是如果单独开一个数组去存放就正确了,这是为什么?
原代码如下
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+5;
int N,R,Q;
struct Competitor
{
int number;
int store;
int strength;
};
bool cmp(Competitor x,Competitor y)
{
if(x.store == y.store)
{
return x.number < y.number;
}
return x.store > y.store;
}
Competitor arr[MAXN],win[MAXN],lose[MAXN];
int w[MAXN];//实力要单独写一个数组表示,否则答案错误
void MergeSort()//归并排序
{
int i=1,j=1,k=1;
while(i <= N && j <= N)
{
if(win[i].store > lose[j].store || (win[i].store == lose[j].store && win[i].number < lose[j].number))
{
arr[k].store = win[i].store;
arr[k++].number = win[i++].number;
}
else
{
arr[k].store = lose[j].store;
arr[k++].number = lose[j++].number;
}
}
while(i <= N)
{
arr[k].store = win[i].store;
arr[k++].number = win[i++].number;
}
while(j <= N)
{
arr[k].store = lose[j].store;
arr[k++].number = lose[j++].number;
}
}
int main()
{
cin>>N>>R>>Q;
for(int i = 1;i <= 2*N;i++)
{
cin>>arr[i].store;
arr[i].number = i;
}
for(int i=1;i <= 2*N ; i++)
{
cin>>arr[i].strength;
}
sort(arr + 1 , arr + 1 + 2*N , cmp);
while(R--)
{
int flag=1;
for(int i = 1;i <= 2*N ;i+=2)
{
if(arr[i].number>arr[i+1].number)//胜者进胜组,败者进败组
{
win[flag].store = arr[i].store+1;
win[flag].number = arr[i].number;
lose[flag].store = arr[i+1].store;
lose[flag].number = arr[i+1].number;
flag++;
}
else
{
win[flag].store = arr[i+1].store+1;
win[flag].number = arr[i+1].number;
lose[flag].store = arr[i].store;
lose[flag].number = arr[i].number;
flag++;
}
}
MergeSort();
}
cout<<arr[Q].number;
return 0;
}