专栏文章

AT_arc144_b 题解

II_like_magic
AT_arc144_b题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqkesl9
此快照首次捕获于
2025/12/04 06:14
3 个月前
此快照最后确认于
2025/12/04 06:14
3 个月前
查看原文
这道题其实不难。
这是一道简单的二分答案题。
我们要求出 AA 数列最小值的最大值可能值，那么我们可以二分答案。
首先，假定答案为 mm，那么，原 AA 数列中小于 mm 的值都要通过若干次 Ai←Ai+aA_i \gets A_i + a 操作使其大于等于 mm。具体操作次数为至少 ⌈m−Aia⌉\lceil\frac{m - A_i}{a}\rceil。
那么我们对数列中每个小于 mm 的数求出最少操作次数，并求和，得到的即为总共的最少操作次数，记为 LL。
接下来，我们看向数列中大于 mm 的数字，这些数字可以进行若干次 Ai←Ai−bA_i \gets A_i - b 操作，但是我们要保证操作完 Ai≥mA_i \ge m，于是我们可以求出它们的最多操作次数，即为 ⌊Ai−mb⌋\lfloor\frac{A_i - m}{b}\rfloor。
同样对它们求和，得到总共的最多操作次数，记为 RR。
由于两种操作是合并在一起的，所以一种操作的次数就是总操作次数。
显然，最小操作次数应当是小于等于最大操作次数的，所以如果 L>RL > R，那么这个答案 mm 就是不合法的。
然后就完成二分的 check 函数了。
接下来就是模板了。
注意要开 long long，运算过程中可能会爆 int。
复杂度为 O(nlog⁡m)O(n\log m)，mm 为数字的值域。
代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...