AT_yahoo_procon2018_qual_e题解

· · 题解

第一个对！

翻译有误，

正确的翻译：

捞。

解题思路：

需要判断一下度数总和的奇偶性。

如果总和是奇数，那就说明没有办法满足条件，输出 ABSOLUTELY NO。

反之，可能是满足条件的图。

接下来我们需要看一下是否有顶点的度数超过了所有顶点度数的一半。

如果有这样的顶点，那就无论如何都无法通过增加其他顶点的度数来满足条件，则输出 NO。

我们再来看一下是否有 1 个顶点的度数 \le 度数总和的一半。

如果有这样的顶点，那就无法通过增加顶点的度数来满足条件，则输出 NO 。反之，输出 YES。

具体内容看一下代码吧。

代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int d[n];
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
        sum += d[i];
        sum %= 2;//计算总度数的奇偶性
    }
    sort(d, d + n, greater<int>());
    if (sum % 2 == 1) {
        d[0] --;
        sort(d, d + n, greater<int>()); /*如果总度数是奇数，那么说明图中有奇数个边。为了使图成为简单图，需要将其中的一条边删除。因此，将度数最大的顶点的度数减去1，以达到删除一条边的效果。
然后，倒序排序，目的是确保度数最大的顶点仍然处于数组的第一个位置，以便后续的计算/*/
    }
    int z = 0;
    for (int i = 0; i < n; ++i) {
        if (d[i] != 0) {
            z = i + 1; //得到有度数的顶点的数量。
        }
    }
    long long s[z+1];
    int cop[z];
    s[0] = 0;
    for (int i = 0; i < z; ++i) {
        s[i + 1] = s[i] + d[i];
        cop[z - 1 - i] = d[i];//为准备后续的计算步骤。
    }
    bool possible = true;
    for (int i = 1; i <= z; ++i) {
        long long c = (long long)i * (i - 1) - s[i];
        int id = upper_bound(cop, cop + z, i) - cop;
        id = z - id;
        id = max(id, i);
        c += (long long)(id - i) * i + s[z] - s[id];
        if (c < 0) {
            possible = false;
            break;
        }
    }
    if (possible) {
        if (sum % 2 == 1) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    } else {
        cout << "ABSOLUTELY NO" << endl;
    }
    return 0;
}