Election of the King 2023牛客暑期多校训练营4-F

登录—专业IT笔试面试备考平台_牛客网

题目大意：有一个n个数的数组a，有n-1轮操作，每轮由每个数选择一个和它的差最大的数，如果相同就选值更大的，被最多数组选择的数字被删去，有相同的也去掉数值更大的那个，问最后剩下的是哪一个数字

1<=n<=1e6;1<=ai<=1e9

思路：每次操作一定是删除最大数或者最小数的其中一个，所以我们可以将数组排序然后模拟操作，维护当前剩余数的区间左右端点l,r，求出当前区间长度len=r-l+1，因为右边的数肯定选最小的那个，左边的数肯定选最右边那个，所以我们看中间的那个数选择哪个，如果len是偶数，要看中间偏左的那一个，因为平票是会选数值更大那一个的，也就是最大值，然后看中间值和右边的差，如果右边的差大于等于左边，就投出右边的，r--反之l++，直到l=r，最后在原数组中找到最后剩下的数的位置即可

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
int a[N];
int b[N];
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];b[i] = a[i];//保留原数组}sort(a + 1, a + n + 1);int l = 1, r = n;while (l < r){int len = r - l + 1;int pos = len / 2 + l;if (len % 2 == 0)pos--;//偶数时要选左边的if (a[r] - a[pos] >= a[pos] - a[l]){//右边差大于左边或者平票都是投出最右边的r--;}elsel++;}for (int i = 1; i <= n; i++){if (b[i] == a[l])//在原数组中找到最后剩下的数{cout << i << endl;break;}}return 0;
}