二分查找+优先队列
先看要求：寻找r[i]值，使得在【i,r[i]】区间内数组A的和<=k[i]c[i],在【i,r[i]+1】数组A的和>k[i]c[i]，且r[i]的取值在[i-1,n]
这个可以利用前缀和s数组来二分查找，寻找r[i]的值，利用函数upper_bounder(s+i,s+1+n,k[i]*c[i]+s[i-1])-s-1；
然后看满意度：满意度为B数组中最大元素-最小元素。
我们可以这么想，只要把最小元素变大，那么满意度就会变小，当然其间满意度可能会变大，我们取最小即可
很容易想到，我们可以利用优先队列存储B元素和它的下标，每次取出最小B元素使其变大即可
这样我们只需要维护最大值，然后减去优先队列里的最小值即可
不难想到，要让B[i]元素变大，我们需要让r[i]元素变大，要让r[i]元素变大，我们需要让k[i]*c[i]值变大，所以每次让c[i]++，即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int read(){//快读
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
#define LL long long
const int N=2e5+10;
int a[N],b[N],c[N],k[N],r[N];
LL s[N];//前缀和数组
int main(){
int n=read(),m=read();
for(int i=1;i<=n;i++) {
a[i]=read();
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++) k[i]=read();
for(int i=1;i<=n;i++) c[i]=read();
priority_queue<pair<int,int>> q;//默认根据first排序
int mx=0;
for(int i=1;i<=n;i++){
r[i]=upper_bound(s+i,s+1+n,k[i]*c[i]+s[i-1])-s-1;//寻找r的值
b[i]=r[i]-i+1;
mx=max(b[i],mx);
q.push({-b[i],i});//因为优先队列默认是大根堆，所以取反就是小根堆了
}
int ans=mx+q.top().first;
while(m--){
auto u=q.top();q.pop();
int indx=u.second;
c[indx]++;
r[indx]=upper_bound(s+indx,s+1+n,k[indx]*c[indx]+s[indx-1])-s-1;//更新r值
b[indx]=r[indx]-indx+1;//更新b的值
mx=max(mx,b[indx]);//维护最大值
q.push({-b[indx],indx});
ans=min(ans,mx+q.top().first);//更新ans
}
cout<<ans;
return 0;
}