[ABC270E] Apple Baskets on Circle 题解

FFTotoro · 2022-10-21 17:11:43 · 题解

赛时二分答案调挂了，因为这题细节很多……希望大家引以为戒，二分答案时一定要注意答案到底是 l 还是 mid，check 函数判断合法性要用 \le 还是 <，以及各类其他问题。

本题容易看出我们可以二分答案高桥君吃的“圈数”，如果完整地吃了 x 圈那么每一个篮子中的苹果数量就变为 \max\{a_i-x-1,0\} 或 \max\{a_i-x,0\}。至于到底是哪一个，取决于吃完 x 圈后数量是否不到 k，这个地方判断一下即可。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,k,x,l=0,r=0; cin>>n>>k;
  vector<int> a(n);
  for(auto &i:a)cin>>i,r=max(r,i); // 求出答案上限 r
  while(l<=r){
    int mid=l+r>>1,c0=0;
    for(auto &i:a)c0+=min(i,mid); // 判断每个篮子能吃多少个
    if(c0>k)r=mid-1;
    else l=mid+1,x=mid; // 调端点
  }
  for(auto &i:a)k-=min(i,x);
  for(auto &i:a){
    if(k>0){ // k 是否还有剩
      if(i-x-1>=0)cout<<i-x-1<<' ',k--; // 这一个篮子还剩下苹果，如下同理
      else cout<<"0 "; // 没剩下任何苹果
    }
    else cout<<max(i-x,0ll)<<' ';
  }
  return 0;
}