CF1856B Good Arrays 题解

liruixiong0101 · 2023-08-06 12:44:00 · 题解

P0 题意：

给出一个长度为 n 的正整数序列 a，让你求出是否有一个长度为 n 的正整数序列 b 满足以下条件：

1. a_i\neq b_i(i\in[1,n])
2. \sum_{i=1}^{n} a_i=\sum_{i=1}^{n} b_i

P1 思路：

1.我的错误思路：

一开始我想到了错位，将 a 序列错排到 b 序列，也就是需要比较每个数出现的数量，但是这样的思路狠明显是错的，因为有些序列，你可以通过变换值的大小从而得到一个合法序列。

2.正确思路：

（我也不知道我的思路对不对捏。

由于此题的序列为正整数序列，所以我们肯定会想到让前 n-1 个值为最小，这样就可以让最后一个值变为最大，也就是尽量不要让最后一个值为非正数，若最后一个值为非正数，那么输出 NO。操作如下：

• 若 a_i=1：b_i:=2。
• 若 a_i\neq1：b_i:=1。

很容易发现一个东西，若 a_n\neq b_n 一定合法，但若 a_n=b_n，这样的情况只能调动前面的数，有两种情况可以考虑：

• 将 b_n:=b_n+1：这样只能让 b_i:=b_i-1(i\in[1,n))，这样又可以分为两种情况：

  • 若 b_i=1：b_i-1=0，不合法。
  • 若 b_i=2，则 a_i=1：b_i-1=a_i，不合法。

  这种情况是不可能出现的。

• 将 b_n:=b_n-1：这种情况必须先保证 b_n\neq1，接着只能让 b_i:=b_i+1(i\in[1,n))，这样只要出现了一个 i(i\in[1,n))，b_i+1\neq a_i 那么就一定合法。

P3 代码：

代码就很好实现了，代码如下：

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e5 + 5;

int T, n;
LL suma, sumb, a[kMaxN], b[kMaxN];

int main() {
  for (cin >> T; T; T--, suma = sumb = 0) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i], suma += a[i];
    }  // 输入序列a，记录序列a的元素总和
    for (int i = 1; i < n; i++) {
      b[i] = a[i] == 1 ? 2 : 1;  // 计算出b[1...n-1]
      sumb += b[i];              // 记录b[1...n-1]的和
    }
    if (sumb >= suma) {  // b[n]<=0
      cout << "NO\n";
      continue;
    }
    b[n] = suma - sumb;
    if (a[n] == b[n]) {  // 判断最后一位是否相同
      bool f = 0;
      for (int i = 1; i < n; i++) {
        if (b[i] + 1 != a[i] && b[n] > 1) {
          cout << "YES\n", f = 1;
          b[i]++, b[n]--;
          break;
        }
      }
      cout << (!f ? "NO\n" : "");
    } else {
      cout << "YES\n";
    }
  }
  return 0;
}

AC 记录：https://codeforces.com/contest/1856/submission/217407090