题解 | #谁是说谎者#(C++)

D 谁是说谎者

题面中有说“说谎组中至少有……位选手说谎了”

而我们看到输入描述的上一行里还有一句

“已知说谎组中至少有3位选手说谎了。你能侦破说谎选手的编号吗？”

再一看，说谎者一共有n+1位，而题目输入里只给出了n位说谎者

说明什么，第n+1位说谎者说的内容是“已知说谎组中至少有3位选手说谎了。”

那么显而易见了，题目里藏了一个说谎者，然后正常做题就可以了

void Aiden()
{
  ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, cnt = 0, x, y, z, len, t, l, r, cur;
  string s1, s2;
  cin >> n;
  vector<ll> a(n + 2);
  for (ll i = 1; i <= n; i++)
      cin >> a[i];
  a[n + 1] = 3;
  for (ll cnt = 0; cnt <= n + 1; cnt++)
  {
      vector<ll> liars;
      for (ll i = 1; i <= n + 1; i++)
      {
          if (cnt < a[i])
              liars.push_back(i);
      }
      if (liars.size() == cnt)
      {
          cout << cnt;
          for (auto x : liars)
              cout << " " << x;
          cout << endl;
          return;
      }
  }
  cout << -1 << endl;
}

时间复杂度O(n^2),比出题人的代码要优秀啊