题解归档 - cf2222D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2222D
• 本地来源：problems/cf2222D/idea.md
• 题目链接：https://codeforces.com/contest/2222/problem/D
• 原始标题：cf2222D - Permutation Construction

思路

cf2222D - Permutation Construction

Pattern

Let s_i = a_1 + ... + a_i and s_0 = 0.

For positions i < j, the inversion contributes:

a_i + ... + a_{j-1} = s_{j-1} - s_{i-1}.

Choosing a permutation is equivalent to choosing the order of positions from
larger value to smaller value. For pair (i,j):

• if s_{i-1} < s_{j-1}, putting i before j gains a positive value;
• if s_{i-1} > s_{j-1}, putting j before i avoids a negative value;
• if equal, either order is equivalent.

Thus every pair agrees with one global transitive order: positions sorted by
nondecreasing prefix sum.

Algorithm

Sort positions 1..n by (s_{i-1}, i). Assign values n,n-1,...,1 in that
order.

Checks

• python tools/math_reasoning_search.py --problem cf2222D -n 8 - required
  constructive precheck done.
• python tools/run_exe.py cf2222D - sample OK.
• python tools/stress2.py cf2222D -n 500 --keep-fail - OK against
  exhaustive permutation brute with checker.cpp.

代码

来源：problems/cf2222D/solution.cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<ll> pref(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            ll x;
            cin >> x;
            pref[i] = pref[i - 1] + x;
        }

        vector<int> pos(n);
        iota(pos.begin(), pos.end(), 1);
        sort(pos.begin(), pos.end(), [&](int x, int y) {
            if (pref[x - 1] != pref[y - 1]) return pref[x - 1] < pref[y - 1];
            return x < y;
        });

        vector<int> p(n + 1);
        for (int i = 0; i < n; i++) {
            p[pos[i]] = n - i;
        }
        for (int i = 1; i <= n; i++) {
            if (i > 1) cout << ' ';
            cout << p[i];
        }
        cout << '\n';
    }
    return 0;
}