每日一题：Game Strategy

题意

三个人玩游戏，每个人最开始都有 $n$ 个数，开始轮流删数，直到最后每个人只剩下一个数。第一个人想让这三个数的和（$x+y+z$）加起来尽量大，第二个想尽量小，第三个想尽量接近0。每个人都以自己的想法为策略，问最后得到的三个数的和是多少（$n<=100$）。

solution

不要想复杂了，其实就是直接模拟。暴力枚举三个数，因为第三个人想尽量接近 0，因此枚举 $z$ 时维护最接近 0 的解 $m1$，因为第二个人想要最小值，因此取枚举所有 $z$ 得到的解（$m1$）的最小值$m2$，然后第一个人想要最大值，所以取枚举所有 $y$ （$m2$）的最大值 $m3$。

Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
int main() {
  int n, a[105], b[105], c[105], d[105];
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  for (int i = 0; i < n; i++) cin >> c[i];
  int m1 = -INF, m2, m3;
  for (int i = 0; i < n; i++) {
    m2 = INF;
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) d[k] = a[i] + b[j] + c[k];
      sort(d, d + n);
      int pos = lower_bound(d, d + n, 0) - d;
      if (pos == n)
        m3 = d[pos - 1];
      else if (pos == 0)
        m3 = d[0];
      else {
        if (d[pos] > -d[pos - 1])
          m3 = d[pos - 1];
        else
          m3 = d[pos];
      }
      m2 = min(m2, m3);
    }
    m1 = max(m1, m2);
  }
  cout << m1 << '\n';
  return 0;
}