题解 CF1490G 【Old Floppy Drive】
绝顶我为峰
2021-02-17 14:31:47
显然每走一圈贡献是一定的，计算一下前缀和即可。
记前缀和为 $sum[i]$，$maxn[i]$ 为 $a[1]\sim a[i]$ 的起点为 1 的子串权值最大值，显然有 $maxn[i]=\max(maxn[i-1],sum[i])$。
第一圈就满足要求的（$maxn[n]\geq x$）可以特殊处理一下，这样特判的时候不容易出错。
然后特判无解，充要条件 $sum[n]\leq0$ 且 $x>0$。
剩下来的就是走了不止 1 圈的情况。我们可以二分圈数，每次 check 走 $mid+1$ 圈后能否满足条件，即 $sum[n]\times mid+maxn[n]\geq x$（因为第 $mid+1$ 圈可能走到图中就满足条件所以最后一圈贡献并不是 $sum[n]$ 而是 $maxn[n]$）。
然后二分得到圈数 $ans+1$，那么显然前 $ans$ 圈是走完整的，而最后一圈不一定，于是在 $maxn[]$ 数组上二分就好了，答案为$ans\times n+lower\_bound(maxn+1,maxn+n+1,x-ans\times sum[n])-maxn-1$。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int t,n,m,a[200001],sum[200001],maxn[200001];
signed main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
maxn[0]=-1e18;
sum[0]=0;
for(register int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
maxn[i]=-1e18;
maxn[i]=max(maxn[i-1],sum[i]);
}
while(m--)
{
int x;
scanf("%lld",&x);
if(maxn[n]>=x)
{
printf("%lld ",(long long)(lower_bound(maxn+1,maxn+n+1,x)-maxn-1));
continue;
}
if(sum[n]<=0&&x>0)
{
printf("-1 ");
continue;
}
int l=0,r=1e9,mid,ans=1e9;
while(l<r)
{
mid=(l+r)>>1;
if(mid*sum[n]+maxn[n]>=x)
{
r=mid;
ans=mid;
}
else
l=mid+1;
}
printf("%lld ",(long long)(ans*n+(long long)(lower_bound(maxn+1,maxn+n+1,x-ans*sum[n])-maxn-1)));
}
puts("");
}
return 0;
}
```