题解
首先计算出每个水缸里的水能喝几次, 然后推出一个结论: 水少的水缸如果喝了 $n$ 次, 则水比它多的水缸也至少喝了 $n$ 次.
继续推还可以推出: 如果某一轮从某个水缸一直到结尾还能喝 $k$ 次, 而且该还能喝的次数 $\geq k$ , 则水比该水缸多的水缸不会在本轮被喝完.
然后我们就可以把水缸按照还可以喝的次数升序排序, 树状数组维护查询某水缸到结尾还能喝几次, 贪心处理即可
参考代码
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> const int MAXN=1e6+; int n;
int m;
int x;
int r;
int ans;
int cnt;
int last;
int c[MAXN]; std::pair<int,int> a[MAXN]; int Query(int);
int LowBit(int);
void Add(int,int);
void Initialize();
int BinarySearch(int); int main(){
Initialize();
for(int i=;i<=cnt;i++){
if(a[i].first<ans){
Add(a[i].second,-);
}
else{
int tmp=Query(cnt)-Query(last);
while(r<m&&ans+tmp<=a[i].first){
r++;
ans+=tmp;
last=;
tmp=Query(cnt)-Query(last);
}
if(r>=m)
break;
int pos=BinarySearch(a[i].first-ans);
ans=a[i].first;
last=pos;
Add(a[i].second,-);
}
}
printf("%d\n",ans);
return ;
} int BinarySearch(int x){
int ans=last,l=last,r=cnt;
while(l<=r){
int mid=(l+r)>>;
if(Query(mid)-Query(last)<=x){
ans=mid;
l=mid+;
}
else
r=mid-;
}
return ans;
} void Initialize(){
int tmp;
scanf("%d%d%d",&n,&m,&x);
for(int i=;i<=n;i++){
scanf("%d",&a[i].first);
a[i].second=i;
}
for(int i=;i<=n;i++){
scanf("%d",&tmp);
a[i].first=(x-a[i].first)/tmp+;
}
for(int i=;i<=n;i++){
if(a[i].first!=){
a[++cnt]=a[i];
Add(a[i].second,);
}
}
std::sort(a+,a++cnt);
} void Add(int i,int x){
while(i<=n){
c[i]+=x;
i+=LowBit(i);
}
} int Query(int x){
int ans=;
while(x>){
ans+=c[x];
x-=LowBit(x);
}
return ans;
} inline int LowBit(int x){
return x&-x;
}
Backup