[题解]P6927 [ICPC2016 WF] Swap Space

WaterSun · 2024-08-12 14:28:11 · 题解

更好的阅读体验

怎么没有人证明贪心啊。

思路

显然要按 a_i,b_i 的大小关系分类：

假令有两对数 (a_1,b_1),(a_2,b_2)，且 a_1 \leq a_2。

• 如果 b_1 \geq a_2。则按照 12 的顺序，将带来 a_1 的花费；而按照 21 的顺序，将带来 a_2 的花费。所以按照 12 顺序更优。

• 如果 b_1 < a_2。则按照 12 的顺序，将带来 a_1 + a_2 - b_1 的花费；而按照 21 的顺序，将带来 a_2 的花费。因为 a_1 - b_1 < 0，所以按照 12 顺序更优。

综上，此时按照 a_i 从小往大排序正确。

假令有两对数 (a_1,b_1),(a_2,b_2)，且 b_1 \geq b_2：

• 如果 b_1 \geq a_2。则按照 12 的顺序，将带来 a_1 的花费；而按照 21 的顺序，将带来 a_2 + a_1 - b_2 的花费。因为 b_2 - a_2 < 0，所以按照 12 顺序更优。

• 如果 b_1 < a_2。则按照 12 的顺序，将带来 a_1 + a_2 - b_1 的花费；而按照 21 的顺序，将带来 a_2 + a_1 - b_2。因为 b_2 - b_1 < 0，所以按照 12 顺序更优。

综上，此时按照 b_i 从大往小排序正确。

Code

#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define int long long

using namespace std;

typedef pair<int,int> pii;
const int N = 1e6 + 10;
int n,ans,cnt;
vector<pii> A,B;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

signed main(){
    n = read();
    for (re int i = 1,a,b;i <= n;i++){
        a = read(),b = read();
        if (a <= b) A.push_back({a,b});
        else B.push_back({a,b});
    }
    sort(A.begin(),A.end(),[](const pii &a,const pii &b){
        if (a.fst != b.fst) return a.fst < b.fst;
        else return a.snd > b.snd;
    });
    sort(B.begin(),B.end(),[](const pii &a,const pii &b){
        if (a.snd != b.snd) return a.snd > b.snd;
        else return a.fst < b.fst;
    });
    for (pii p:A){
        if (cnt >= p.fst){
            cnt -= p.fst; cnt += p.snd;
        }
        else{
            ans += (p.fst - cnt); cnt = p.snd;
        }
    }
    for (pii p:B){
        if (cnt >= p.fst){
            cnt -= p.fst; cnt += p.snd;
        }
        else{
            ans += (p.fst - cnt); cnt = p.snd;
        }
    }
    printf("%lld",ans);
    return 0;
}