CF1890D Doremy's Connecting Plan

或许赛时根本不需要证明贪心的正确性。

我们发现 \(c\) 对于问题的影响不大，我们可以将每个 \(a_i\) 除以 \(c\)，就转化为了 \(c=1\) 的情况。

一个自然的贪心是用 \(1\) 作为中心点去连接其他的所有点，这需要两条结论保证其正确性：

结论一： 如果当前图中还可以连边，点 \(1\) 就还可以与其他点连边。

假设我们能够在点 \(i,j \ne 1\) 之间连边的话，有以下不等式成立 \(S_i+S_j\ge i\cdot j\ge i+j\)，其中 \(S_i\) 表示点 \(i\) 所属连通块的点权和（第二个不等号可以通过简单的数学推导得出）。此时必有 \(S_i\ge i\) 或者 \(S_j\ge j\)（反证法，若 \(S_i<i\) 且 \(S_j<j\) 则 \(S_i+S_j<i+j\)，矛盾）。不妨设 \(S_i\ge i\)，有 \(S_i+S_1\ge i\cdot 1\)，所以 \(1,i\) 之间一定可以连边。

结论二： 以点 \(1\) 为中心点连边，不会导致“本来能连上的点”连不上了。

假如点 \(i,j\) 之间能连边，由结论一得，必有 \(1,i\) 或 \(1,j\) 之间能连边，则任意点都能与 \(1\) 间接连通，但能否直接连通呢？难以证明。

就本题而言，我们继续贪心地认为，只要 \(1\) 连接起来的连通块足够大，点权和就能够保证不等式的成立。所以可以把节点按照 \(S_i-i\) 从大到小排序，先易后难（显然 \(S_i-i\) 大时不等式 \(S_i+S_1\ge i\cdot 1\) 更容易成立），逐一与点 \(1\) 结合，如果不能结合则认为无法连通，输出 NO。

下面是 AC 代码：

void solve() {
    int n;
    i64 c;
    cin >> n >> c;
    cin >> $( a, n );
    iota( all( b, n ), 1 );
    sort( all( b, n ), [&]( int x, int y ) {
        return a[x] - x * c > a[y] - y * c;
    } );
    i64 s = a[1];
    forn( i, n ) {
        if( b[i] == 1 ) ctn;
        if( s + a[b[i]] < b[i]*c ) {
            cout << "No\n";
            return;
        }
        s += a[b[i]];
    }
    cout << "Yes\n";
    clear();
}

THE END