题解：洛谷 P1843 奶牛晒衣服

• 标签：二分，贪心

题意

给定一个数列，每秒可以将所有数减 \(a\)，也可以选择一个数减 \(b\)，二者可同时进行，求让所有数小于等于 \(0\) 的最小秒数。

思路

要求最小的秒数，也就是刚好所有数字小于等于 \(0\)，且尽量大。

这个秒数具有单调性，考虑二分答案。

二分的过程自然是 \(O(\log n)\) 的，所以判断左右区间的函数必须在 \(O(n)\) 以内完成。

对于每一个 \(w_i\)，有两种：

• 如果 \(w_i-m\cdot a<=0\)，说明目前就单靠 \(a\) 就能实现；
• 否则就要用一定的 \(b\)，那就是 \(\lceil\frac{w_i-m\cdot a}{b}\rceil\)。

假如最后 \(b\) 的使用超过了 \(m\)，那说明不行，否则就是可以的。

二分的边界一直很神奇，需要多加注意。

代码

#include<bits/stdc++.h>
#define i64 long long
#define L(a,b,c) for(int i=a;i<=b;i+=c)
#define R(a,b,c) for(int i=a;i>=b;i-=c)

using namespace std;

const int N=5e5+5,M=998244353;

int n,a,b,w[N];

void solve();

signed main(){
  ios::sync_with_stdio(0);
  
  solve();
  
  return 0;
}

bool check(i64 m){
  i64 k=0;
  L(1,n,1){
    i64 x=w[i]-m*a;
    if(x>0){
      if(x%b!=0) x=x/b+1;
      else x/=b;
      k+=x;
    }
    if(k>m) return 0;
  }
  if(k<=m) return 1;
  return 0;
}

void solve(){
  cin>>n>>a>>b;
  L(1,n,1) cin>>w[i];
  i64 l=0,r=5e5,m;
  while(l<r){
    m=(l+r)/2;
    if(check(m)) r=m;
    else l=m+1;
  }
  cout<<l<<endl;
}