Description：

赤道上有 $n$ 个机场，第 $i$ 个和第 $i+1$ 个之间距离为 $d[i]$ ，然后又 $m$ 次询问，一架最长飞行距离为 $l$ 的飞机环绕迟到最少需要经停几个机场。

$1\leqslant n\leqslant 10^6,1\leqslant m\leqslant 10^2$

Solution：

一个重要的性质是为了让经停机场最少，我们肯定尽量选能够够到的最远的机场，这个可以用双指针求出每个位置的下一个机场，也就是说，每次飞到的下一个位置是固定的，跟之前发生了什么没有关系，正解是把环复制两倍，把第一倍的所有位置的开始位置设成这个位置，然后在第二倍的时候从一个最远能到的位置转移过来，之所以这样做是因为从 $n+1$ 转移过来的位置之间这部分一定有一个可以是一个环的开始，所以我们只要考虑从前半部分第一次就跳到后半部分的情况就行了，然后把开始位置设成那个位置的开始位置，如果这个长度超过一圈了，就更新答案，这样是一定不会丢解的。

感觉很好理解但是很难想到。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 2000010

int l[MAXN];

int sum[MAXN];

int fr[MAXN];

int f[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&l[i]);

	for(int i = 1;i <= n;++i)l[n + i] = l[i];

	for(int i = 1;i <= 2 * n;++i)sum[i] = sum[i - 1] + l[i];

	for(int i = 1;i <= n;++i)fr[i] = i;

	int d;

	for(int k = 1;k <= m;++k)

	{

		int ans = 0x3f3f3f3f;

		scanf("%d",&d);

		bool tag = true;

		for(int i = n + 1,j = 1;i <= 2 * n;++i)

		{

			while(sum[i] - sum[j] > d)++j;

			if(i == j)

			{

				tag = false;

				break;

			}

			f[i] = f[j] + 1;fr[i] = fr[j];

			if(sum[i] - sum[fr[i]] >= sum[n])ans = min(ans,f[i]);

		}

		if(tag)printf("%d\n",ans);

		else puts("NIE");

	}

	return 0;

}