AT_arc144_b 题解

· · 题解

这道题其实不难。

这是一道简单的二分答案题。

我们要求出 A 数列最小值的最大值可能值，那么我们可以二分答案。

首先，假定答案为 m，那么，原 A 数列中小于 m 的值都要通过若干次 A_i \gets A_i + a 操作使其大于等于 m。具体操作次数为至少 \lceil\frac{m - A_i}{a}\rceil。

那么我们对数列中每个小于 m 的数求出最少操作次数，并求和，得到的即为总共的最少操作次数，记为 L。

接下来，我们看向数列中大于 m 的数字，这些数字可以进行若干次 A_i \gets A_i - b 操作，但是我们要保证操作完 A_i \ge m，于是我们可以求出它们的最多操作次数，即为 \lfloor\frac{A_i - m}{b}\rfloor。

同样对它们求和，得到总共的最多操作次数，记为 R。

由于两种操作是合并在一起的，所以一种操作的次数就是总操作次数。

显然，最小操作次数应当是小于等于最大操作次数的，所以如果 L > R，那么这个答案 m 就是不合法的。

然后就完成二分的 check 函数了。

接下来就是模板了。

注意要开 long long，运算过程中可能会爆 int。

复杂度为 O(n\log m)，m 为数字的值域。

代码：

#include<bits/stdc++.h>
#define int long long // 注意要开 long long，运算过程中会爆 int
using namespace std;
const int N = 300005; // 数据范围
int n, a, b;
int A[N];
bool check(int mid) { // 判断 mid 是否合法
    int res = 0;
    for(int i = 1; i <= n; i ++) {
        if(A[i] < mid) {
            int d = mid - A[i];
            res += (d + a - 1) / a; // 至少操作次数
        } else {
            int d = A[i] - mid;
            res -= d / b;  // 至多操作次数
        }
    }
    // res 即为两者的差，如果差小于等于 0，则为至多操作次数大于至少操作次数，合法，返回 1，否则返回 0
    return res <= 0;
}
signed main() {
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i ++) {
        cin >> A[i];
    }
    int l = 1, r = 1000000000; // 范围
    while(l + 1 < r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            l = mid; // mid 合法，说明答案可能可以更大，答案在 mid 到 r 的范围
        } else {
            r = mid - 1; // mid 不合法，说明这个 mid 偏大了，答案只能在 l 到 mid - 1 的范围
        }
    }
    if(check(r)) cout << r << "\n"; // 如果 r 合法，输出 r
    else cout << l << "\n"; // 否则答案就是 l
    return 0;
}