网站排名查询平台,建设手机网站赚钱吗,交通建设工程质量监督局网站,网店怎么开网店登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;有一个n个数的数组a#xff0c;有n-1轮操作#xff0c;每轮由每个数选择一个和它的差最大的数#xff0c;如果相同就选值更大的#xff0c;被最多数组选择的数字被删去#xff0c;有相同的也去掉数值更大的那个…登录—专业IT笔试面试备考平台_牛客网
题目大意有一个n个数的数组a有n-1轮操作每轮由每个数选择一个和它的差最大的数如果相同就选值更大的被最多数组选择的数字被删去有相同的也去掉数值更大的那个问最后剩下的是哪一个数字
1n1e6;1ai1e9
思路每次操作一定是删除最大数或者最小数的其中一个所以我们可以将数组排序然后模拟操作维护当前剩余数的区间左右端点l,r求出当前区间长度lenr-l1因为右边的数肯定选最小的那个左边的数肯定选最右边那个所以我们看中间的那个数选择哪个如果len是偶数要看中间偏左的那一个因为平票是会选数值更大那一个的也就是最大值然后看中间值和右边的差如果右边的差大于等于左边就投出右边的r--反之l直到lr最后在原数组中找到最后剩下的数的位置即可
//#include__msvc_all_public_headers.hpp
#includebits/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;
}
