题目地址：

https://leetcode.com/problems/determine-if-a-simple-graph-exists/description/

给定一个$n$阶无向无权图每个点的度数组$d$，问该图是否存在。

需要用到Erdős–Gallai theorem，参考https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem。

先将$d$从大到小排序，使得$d_1\ge d_2\ge ...\ge d_n$（假设点编号$1$开始），则图存在当且仅当：

1. ${\sum }_{i=1}^n{d}_i$是偶数；
2. ∀ k , 1 ≤ k ≤ n ⇒ ∑ i = 1 k d i ≤ k ( k − 1 ) + ∑ i = k + 1 n min ⁡ { d i , k } \forall k, 1\le k\le n\Rightarrow\sum_{i=1}^k d_i\le k(k-1)+\sum_{i=k+1}^n\min\{d_i,k\} ∀k,1≤k≤n⇒∑i=1k​di​≤k(k−1)+∑i=k+1n​min{di​,k}

代码如下：

class Solution {
public:
  bool simpleGraphExists(vector<int> &ds) {
    int n = ds.size();
    using ll = long long;
    ll sum = 0;
    for (int x : ds) sum += x;
    if (sum % 2) return false;

    sort(ds.begin(), ds.end(), greater<>{});
    vector<ll> pre(n + 1);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + ds[i];

    for (int k = 1; k <= n; k++) {
      ll left = pre[k];
      ll right = (ll)k * (k - 1);
      int l = k, r = n - 1;
      while (l < r) {
        int mid = (l + r) >> 1;
        if (ds[mid] < k) r = mid;
        else l = mid + 1;
      }
      int j = l;
      
      // [k, j): ds[i] >= k
      // [j, n): ds[i] < k
      right += (ll)(j - k) * k + (pre[n] - pre[j]);
      
      if (left > right) return false;
    }
    return true;
  }
};

时间复杂度$O(n\log n)$，空间$O(n)$。