目录

atcoder D - Widespread

解题思路：

atcoder D - Widespread

题目链接：D - Widespread

题目大意：给你n个正整数,你有一个操作是让一个数减A,然后让其他数减B.保证A > B问你最少多少次操作能够让所有数降到<=0

1≤N≤10^5

1 ≤ B < A ≤ 10^9

1 ≤ h_i ≤ 10^9

解题思路：

题目求操作，肯定是操作越多越容易实现，所以这是一个二分答案后缀模型，左右端点分别为2，1e9（假设所有数为1，假设B为1），用一个ok函数判断mid答案是否合法，在ok函数中判断当前的w[i]是否小于等于b*mid（答案数乘B），如果小于就不用消耗我们的次数（A-B的差值），如果大于的话我们就需要消耗mid次数（这里我用K来存），消耗完之后还要进行一次判断，因为第一次消耗可能是3/2=1，剩下还有一个1没消耗完，所以我们手动还要消耗一次，最后判断一下次数是否变为负数，如果变负数直接返回false，出了for循环就代表k>=0，返回true

这道题给我的教训就是，大数据一定要用long long，这道题为此浪费了半个多小时！！！

#include
using namespace std;

#define ll long long
const ll maxn = 1e5 + 5;
ll n, a, b;
ll w[maxn];

int ok(ll mid)
{
    ll k = mid;
    //遍历所有元素
    for(ll i = 1; i <= n; i++)
    {
        //如果小于mid答案*B就不处理
        if(w[i] <= b*mid)continue;
        //否则就消耗次数
        k -= (w[i]-b*mid) / (a-b);
        //如果碰到不整除的情况就需要手动加一次
        if((w[i]-b*mid) - (w[i]-b*mid)/(a-b)*(a-b) > 0)
            k -= 1;
        //次数如果变为负数就返回false
        if(k < 0)return 0;
    }
    //出了循环就代表k>=0
    return 1;
}

int main()
{
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++)cin >> w[i];
    //假设所有数为1，假设B为1,左右端点
    ll l = 1, r = 1e9;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        //检查答案是否合法
        if(ok(mid))r = mid - 1;
        else l = mid +1;
    }
    //这是一个二分答案后缀模型
    cout << l;
    return 0;
}

​