题解-Codeforces Round 1051 (Div. 2)

幸好是一发没 WA，要是再做快一点就好了。

题目链接

A

数据范围不大，直接暴力

void solve() {
    int n; cin >> n;
    vi v(n);
    int mx = n;
    for(int i = 0; i < n; ++ i) {
        cin >> v[i];
    }

    int idx = 1, cnt = 0;
    for(int i = 0; i < n; ++ i) {
        for(int j = 0; j < n; ++ j) {
            if(v[j] != mx) continue;
            cnt = 0;
            while(j < n && v[j] == mx) {
                v[j ++] --;
                cnt ++;
            }
            if(cnt != idx) {
                NO;
                return;
            }
            idx ++;
            mx --;
            break;
        }
    }
    YES;
}

B

贪心。尽可能使用区间小的折扣劵，对尽可能贵的部分使用，排个序就行。注意可能劵的数量不够，需要格外全额购买价格低的剩余的物品

void solve() {
    int n, k; cin >> n >> k;
    vi v(n);
    for(int i = 0; i < n ;++ i) cin >> v[i];

    vi m(k);
    for(int i = 0; i < k; ++ i) cin >> m[i];

    sort(all(v), greater<int>());
    sort(all(m));

    int idx = 0, ans = 0;
    for(int i = 0; i < k; ++ i) {
        int num = m[i];
        for(int i = 0; i < num; ++ i) {
            if(i != num - 1) {
                ans += v[idx];
            }
            idx ++;
            if(idx >= n) break;
        }
        if(idx >= n) break;
    }
    for(int i = idx; i < n; ++ i) {
        ans += v[i];
    }
    cout << ans << "\n";
}

C

将较小的数指向较大的数，形成一张图，然后拓扑排序

具体来说：$$if (x > y) : v \to u$$$$else: u \to v$$
构成一张图，对拓扑序的每一个元素表示的位置依次递增

void solve() {
    int n; cin >> n;
    vvi G(n + 5);
    vi din(n + 5), tp;

    for(int i = 0; i < n - 1; ++ i) {
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        if(x > y) {
            G[v].push_back(u);
            din[u] ++;
        } else {
            G[u].push_back(v);
            din[v] ++;
        }
    }

    function<void()> toposort = [&]() {
        queue<int> q;
        for(int i=1;i<=n;++i) 
            if(din[i]==0) q.push(i);
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            tp.push_back(x);
            for(auto c : G[x]) 
                if(--din[c] == 0) q.push(c);
        }
        return tp.size() == n;
    };

    toposort();

    int idx = 1;
    vi ans(n + 5);
    for(int i: tp) 
        ans[i] = idx ++;
    
    for(int i = 1; i <= n ;++ i) 
       cout << ans[i] << " \n"[i == n];
}