Solution

​ 首先，如果三日日每次睡觉能恢复的体力甚至不小于一天的消耗，那么三日日只要撑过第一天的工作，就可以无限工作下去，此时输出 $-1$ ；但是如果三日日撑不到睡觉的时候，那就和接下来所要讨论的情况相同。三日日睡觉恢复体力比一天的消耗要小，那么可以对这 $n$ 件事所要消耗的体力求和，设为 $sum$ ，则每天可以视为消耗 $sum$ 体力，再回复 $b$ 体力。由此可以看出，问题转化成了蜗牛爬井问题，只要不犯“蜗牛爬出井再自己爬回去”的低级错误即可。由此，我们可以知道，在体力耗尽的那一天，三日日那一天刚开始时还剩下多少体力 $t_0$ 。对于朴素做法，直接遍历 $n$ 个事件，能做则体力减去该事件所需体力，否则直接输出上一个事件的下标即可。然而，这样的做法复杂度为 $O(nT)$ ，会超时；优化，则使用前缀和预处理该数组，二分查找数组中最后一个小于等于当天剩余体力值 $t_0$ 的值即可，输出其下标，复杂度可被优化为 $O(n+Tlogn)$ 。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void BiSearch(int l,int r,int *a,int t,int n)
{
	if(l==r)
	{
		if(l!=0) cout<<l<<endl;
		else cout<<n<<endl;
		return;
	}
	int mid=(l+r+1)/2;
	if(a[mid]==t)
	{
		cout<<mid<<endl;
		return;
	}
	if(a[mid]<t) BiSearch(mid,r,a,t,n);
	else BiSearch(l,mid-1,a,t,n);
}

void Solve(int n,int m,int *a)
{
	int t;cin>>t;
	if(m>=a[n])
	{
		if(t<a[n]) BiSearch(0,n,a,t,n);
		else cout<<-1<<endl;
		return;
	}
	if(t<a[n])
	{
		BiSearch(0,n,a,t,n);
		return;
	}
	t=(t-a[n])%(a[n]-m)+m;
	BiSearch(0,n,a,t,n);
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;cin>>n;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    int m;cin>>m;
    int b[n+1];b[0]=0;
    for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i-1];
    int T;cin>>T;
    while(T--) Solve(n,m,b);
    return 0;
}