题目概览

描述

One day Anna got the following task at school: to arrange several numbers in a circle so that any two neighboring numbers differs exactly by 1. Anna was given several numbers and arranged them in a circle to fulfill the task. Then she wanted to check if she had arranged the numbers correctly, but at this point her younger sister Maria came and shuffled all numbers. Anna got sick with anger but what's done is done and the results of her work had been destroyed. But please tell Anna: could she have hypothetically completed the task using all those given numbers?

输入

The first line contains an integer n — how many numbers Anna had (3\leq n \leq 10^5). The next line contains those numbers, separated by a space. All numbers are integers and belong to the range from 1 to 10^9.

输出

Print the single line "YES" (without the quotes), if Anna could have completed the task correctly using all those numbers (using all of them is necessary). If Anna couldn't have fulfilled the task, no matter how hard she would try, print "NO" (without the quotes).

大意

给出 n(3\leq n \leq 10^5) 个不超过 10^9 的正整数，判断是否能够将这些数排成一个环，使得任意相邻的两个数的差都为 1 。

思路

假设这些数能够排成一个合法的环，并令其最小值为起（终）点，顺时针为正方向，那么可以将环分为两部分：

1. 最小值 \rightarrow 最大值，

2. 最大值 \rightarrow 最小值，

先考虑最简情形，即沿着正方向遍历的过程中，第 1 部分始终递增，第 2 部分始终递减。此时最大值和最小值的数量均为 1，而中间值的数量均为 2。

示例：

1 2 3 4 5 4 3 2 (1)

114514 114515 (114514) (注：此类情况不存在中间值)

在保证数组最值不变的情况下，可以再往上述最简情形中增加若干组差值为 1 的数对，这样能保证新的数组仍然能形成一个环。

如何添加：

对于每个新的数对 (x, x+1) ，我们可以将其插入到第一部分的任意一个 x+1 后，这样就会形成一个四元组 (x,x+1,x,x+1) 。显然，四元组内部的元素是满足环的构造条件的。由于四元组的首尾元素和原先的数对相同，因此不会改变和外部元素的差值，从而保证了其仍然是一个合法的环。

有了上述的推论，就可以简便的得出不能形成合法环的情况了。我们可以将数组进行排序，如果有相邻两个数的差值大于 1，那么无论如何这个数组都不能形成一个合法的环（因为成环的一个必要条件是相邻数的差必须为 1）。

如果相邻两数的差值最多为 1，但是某个中间值的数量小于 2（即不满足最简情形），那么说明环中至少有一部分存在两个相邻数的差值大于 1，即不能形成合法的环。

如果能满足最简情形，去除掉数组中组成最简情形的部分和所有差值为 1 的数对，如果数组不为空（即仍然存在一个数或多个两两之间差值至少为 2 的数），那么也不能形成合法的环。

显然，我们只需要判断上述三种不能成环的情况。对于第一种情况，直接排序然后遍历即可；对于第二种情况，我们可以用数组 H 存储每个数在数组中的出现次数（由于数可能非常大，因此需要用到离散化，按从小到大的顺序来存储），判断是否有中间值的出现次数小于 2；对于第三种情况，只需要对 H 跑一遍贪心，去除掉所有相邻差值为 1 的数对，如果最后数组 H 中仍然有数未归零，说明仍然存在一个数或多个两两之间差值至少为 2 的数，它们不能被插入环中。如果 H 全部归零，说明可以形成合法的环。

实现

#include <bits/stdc++.h>
#define CNO cout << "NO\n"
#define CYES cout << "YES\n"
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int n, arr[100010], h[100010] = {0};
ll ans = 0;
string str;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) {
    bool b = true;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> arr[i];
    }
    sort(arr, arr + n);
    int cnt = 0;
    h[0] = 1;
    for (int i = 1; i < n; ++i) {
      if (arr[i] == arr[i - 1]) {
        h[cnt]++;
      } else if (arr[i] == arr[i - 1] + 1) {
        cnt++;
        h[cnt]++;
      } else {
        b = false;
        break;
      }
    }
    h[0]--, h[cnt]--;
    for (int i = 1; i < cnt; ++i) {
      h[i] -= 2;
      if (h[i] < 0) b = false;
    }
    for (int i = 1; i <= cnt; ++i) {
      if (h[i] < h[i - 1]) { // 此情况说明中间必定有至少 1 个数不能加入环中
        b = false;
        break;
      } else {
        h[i] -= h[i - 1];
        h[i - 1] = 0;
        if (!h[i]) i++;
      }
    }
    if (h[cnt]) b = false;
    if (b)
      CYES;
    else
      CNO;
  }
  return 0;
}