[数据结构与算法]Codeforces Round #623

A - Dead Pixel

题意

分辨率为a*b的屏幕上在x,y这个点上出现了坏点，问能展示的最大面积是多少

题解

像素坐标是从0开始的，为了好算我们直接从1开始算

围绕这个点所不在的四个区域内输出最大的就行

Code

ll a, b, x, y;

void solve(){
    cin >> a >> b >> x >> y;
    x++, y++;
    cout << max({(y - 1) * a, (x - 1) * b, (a - x) * b, (b - y) * a}) << endl;
}

B - Homecoming

题意

一个人可以做公交车或者做电车来快速到达站牌

可乘车的规则是若到达j点则必须当前点到j-1点都得是同一个点，最后一个不一定一样

现有p钱，问这个人需要从1号站点走到几号站点才能走车

题解

我们不知道他会从哪里开始坐车，但是我们知道他一定会到达n这个点

同时到达n这个点的剩余的钱数还必须大于等于0

那么我们反向模拟，从n出发，看看到哪个点的时候不能在坐车了

Code

void solve(){
    cin >> a >> b >> p;
    cin >> s;
    int n = s.size();
    s = ' ' + s;
    if(p < a && p < b){
        cout << n << endl;
        re;
    }
    for (int i = n; i >= 2; i--){
        // cout << p << e ndl;
        if(p < a && p < b){
            cout << i << endl;
            re;
        }

        int j = i - 1;
        if(s[i - 1] == 'A'){
            while(j >= 1 && p >= a && s[j] == s[i - 1]){
                j--;
            }
            p -= a;
            i = j + 2;
        }
        else{
            while(j >= 1 && p >= b && s[j] == s[i - 1]){
                j--;
            }
            p -= b;
            i = j + 2;
        }
    }
    cout << 1 << endl;
}

C - Restoring Permutation

题意

给你一个数字n，n是数组b的元素数目，b[i]=min(a[i*2-1],a[i*2])，复原出合法的数组a，并且让a的元素排成的串字典序尽量小，a的元素最小是1，最大时2*n，如果a复原不出来，输出-1

题解

贪心放置，若不能再放了就直接输出-1

Code

void solve(){
    cin >> n;
    vector<int> a, b(n);
    map<int, int> st;

    for (int i = 0; i < n; i++){
        cin >> b[i];
        st[b[i]]++;
    }
    if(count(all(b), 2 * n) != 0){ // 可以不要
        cout << -1 << endl;
        return;
    }

    for(auto i : b){
        a.pb(i);
        int j = i + 1;
        while(j < 2 * n && st[j])
            j++;

        if(j > 2 * n || st[j]){
            // cout << 2 << endl;
            cout << -1 << endl;
            return;
        }
        
        a.pb(j);
        st[j] = 1;
    }

    for(auto i : a)
        cout << i << ' ';
    cout << endl;
}

D - Recommendations

题意

让每本书的个数都不一样的最小代价花费

题解

参考：https://www.bilibili.com/video/BV127411u78f?p=4

我们让所有由重复的数量的书，除了最大的那本以外数量全部加一

直到没有最大的

我们设当前重复数量的总花费为sum，其中的最大花费为mx，那么除了最大的那个其他都增加的花费是sum-mx

Code

int n;
PII a[N];

void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i].x;
    }
    for (int i = 1; i <= n; i++){
        cin >> a[i].y;
    }

    sort(a + 1, a + 1 + n);
    

    int ans = 0;
    int now = 0; // 当前的数量
    int summ = 0; 
    priority_queue<int> q;

    for (int i = 1; i <= n; i++){
        while(q.size() && now < a[i].x){ // now小于a[i].x表示我们现在不能把a[i]放进去
            int mx = q.top();
            ans += summ - mx; // 贡献
            summ -= mx; // 总数已经全部加一了，新的sum发生了变化
            q.pop();
            now++;
        }
        q.push(a[i].y);
        now = a[i].x;
        summ += a[i].y;
    }
    while(q.size()){ // 把最后的都加上
        int mx = q.top();
        ans += summ - mx;
        summ -= mx;
        q.pop();
    }
    cout << ans;
}