\(\color{black}\texttt{A. 党同伐异}\)

题目描述

有 \(N\) 个候选人，每个候选人都有一个不同的政治倾向 \(c_i\)，进行 \(N-1\) 次选举。每轮选举中，所有未被淘汰的候选人给另一个没被淘汰的候选人。每一个候选人会将票投给 \(c_i\) 与自己差的绝对值最大的候选人。如果有多个这样的候选人，选择 \(c_i\) 更大的那个。每一轮中获得票最多的人淘汰，如果有多个这样的候选人，选择 \(c_i\) 更大的那个。问最后剩下哪个候选人。

思路

首先对 \(c_i\) 排序，因为每次淘汰的都是 \(c_i\) 最小或最大的人，所以剩余的候选人都是一个区间 \([l,r]\)。对于每一轮，二分最后一个 \(c_i - c_l\le c_r-c_i\) 的 \(i\)，则 \([l,i]\) 内的人全部投票给 \(r\)，\([i+1,r]\) 的人投票给 \(l\)，比较一下即可。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000001;

struct Node {
  int x, id;
}a[MAXN];

int n, s = 1, t;

int Binary_Search() {
  int l = s, r = t;
  for(; l < r; ) {
    int mid = (l + r + 1) >> 1;
    (a[mid].x - a[s].x <= a[t].x - a[mid].x ? l = mid : r = mid - 1);
  }
  return l;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  t = n;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i].x;
    a[i].id = i;
  }
  sort(a + 1, a + n + 1, [](const Node &a, const Node &b) { return a.x < b.x; });
  for(int i = 1; i < n; ++i) {
    int x = Binary_Search();
    (x - s + 1 < t - x ? s++ : t--);
  }
  cout << a[s].id;
  return 0;
}

总结

水题。