CF671B Robin Hood

kevin1616 · 2023-04-25 14:24:41 · 题解

审题

每天最富的人财富 -1，最穷的人财富 +1（若有相同，随便选一个），求最后的穷人与富人财富的差值最小是多少。

方法

• 【暴力】k 次循环，每一次求出最大值与最小值，将最大值 -1，最小值 +1，最后输出最大值减最小值即可。时间复杂度为 O(nk)，故不可以。

• 【二分答案】可以考虑先求出最大值和最小值，再两者相减即为答案，最大、最小值都可以用二分答案求出。此方法的时间复杂度为 O(n \log n)，此方法可行。

思路

1. 最大值的答案是在平均钱数 \sim 钱数总和之间，使每个人从原来的钱数降到目标钱数所需要的天数是否可行。此部分代码如下：

bool check1(int x){
    int cnt = 0;
    for(int i = 1;i <= n;i++){
        if(c[i] > x) cnt += c[i] - x;
    }
    return cnt <= k;
}

2. 最小值的答案是在 1 \sim 平均钱数之间，使每个人从原来的钱数升到目标钱数所需要的天数是否可行。此部分代码略同上，就不单独展示了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
int c[500005];
int l1,r1;
int l2 = 1,r2;
int sum;
bool check1(int x){ // 最大值的答案
    int cnt = 0;
    for(int i = 1;i <= n;i++){
        if(c[i] > x) cnt += c[i] - x;
    }
    return cnt <= k;
}
bool check2(int x){ // 最小值的答案
    int cnt = 0;
    for(int i = 1;i <= n;i++){
        if(c[i] < x) cnt += x - c[i];
    }
    return cnt <= k;
}
signed main(){
    cin >> n >> k;
    for(int i = 1;i <= n;i++){
        cin >> c[i];
        r1 = max(r1,c[i]);
        sum += c[i];
    }
    l1 = sum / n + (sum % n != 0);
    /*
    也可以这样写：
    if(sum % n == 0) l1 = sum / n;
    else l1 = sum / n + 1;
    */
    r2 = sum / n;
    while(l1 < r1){ // 求最大值
        int mid = (l1 + r1) / 2;
        if(check1(mid)) r1 = mid;
        else l1 = mid + 1;
    }
    while(l2 < r2){ // 求最小值
        int mid = (l2 + r2 + 1) / 2;
        if(check2(mid)) l2 = mid;
        else r2 = mid - 1;
    }
    cout << l1 - l2 << endl;
    // 其实这里的 l 也可以替换成 r
    return 0;
}

不抄题解，从我做起！