Train Hard, Win Easy

Created by LXC on Fri Jun 23 23:22:28 2023

https://codeforces.com/problemset/problem/1043/E

ranting: 1900

tag: constructive algorithms, greedy, math, sortings

problem

现在有一场两道题的比赛

给出n个人的两道题的罚时。

现在需要两个人组队完成两道题，每人各一道题，完成的罚时越小越好。

此外给出了m对数，每一对a和b，代表a和b不想组队。

问每个人所有组队情况的罚时总和。

solution

设第i个人两道题的罚时分别是$x_i, y_i$。

我们按照$x_i-y_i$升序排序。

这样对于i和j组队，当$j < i$时，罚时为$x_j+y_i$；当$i < j$时，罚时为$x_i+y_j$。

通过处理y的后缀和，x的前缀和。可以$O(1)$计算出每人与其他人的组队罚时总和。

然后对于每人不想组队的人，删除与其组队的贡献。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> v(n);
    for (auto& [i, j] : v)
        cin >> i >> j;
    vector<ll> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return v[x].first - v[x].second < v[y].first - v[y].second;
    });
    // for (int i : idx) {
    //     cout << v[i].first << " " << v[i].second << "\n";
    // }
    vector<ll> pre(n), suf(n);
    pre[0] = v[idx[0]].first;
    for (int i = 1; i < n; i++) {
        pre[i] = pre[i - 1] + v[idx[i]].first;
    }
    suf[n - 1] = v[idx[n - 1]].second;
    for (int i = n - 2; i >= 0; i--) {
        suf[i] = suf[i + 1] + v[idx[i]].second;
    }
    vector<ll> ans(n);
    for (int i = 0; i < n; i++) {
        ans[idx[i]] = (suf[i] - v[idx[i]].second) +
                      (n - i - 1) * v[idx[i]].first +
                      (pre[i] - v[idx[i]].first) + i * v[idx[i]].second;
    }
    // for (auto i : ans) {
    //     cout << i << " ";
    // }
    // cout << "\n";
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        ll sub = min(v[x].first + v[y].second, v[x].second + v[y].first);
        ans[x] -= sub;
        ans[y] -= sub;
    }
    for (auto i : ans) {
        cout << i << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}