7485-旅行问题

题目传送
环形问题，先破环成链，即用$2$倍长度的线性序列代替环形。
例如，假设$n=5$，环形序列为$1$,$2$,$3$,$4$,$5$，$2$倍长度序列为$1$,$2$,$3$,$4$,$5$,$1$,$2$,$3$,$4$,$5$。
序列编号为$1$到$10$，则求从编号$1$的点顺时针出发能否回到编号$1$的点，就是求从编号$1$的点出发能否到达编号$6$的点，求从编号$5$的点逆时针出发能否回到编号$5$的点，就是求从编号$10$的点出发能否到达编号$5$的点。
能否到达取决于油量是否够，所以途中的任意一个加油站，油量必须大于等于路程，才能到达下一个加油站。
设$p[i]$表示第$i$个加油站可以加的油量，$d[i]$表示从第$i$个点走到第$i+1$个点的路程，则$p[i]-d[i]$就表示从第$i$个点到第$i+1$个点油量的增减情况。
先考虑顺时针情况，$s[i]=s[i-1]+p[i]-d[i]$表示剩余油量的前缀和，也就是说$s[i]$表示刚走到第$i+1$个点还未加油时汽车的剩余油量，如果油是负数，则说明无法到达。
那么在区间$[i,n+i]$共$n$个加油站，每个站点的剩余油量都不能为负数，否则无法到达。所以会想到枚举这些区间和，如果油负数，则无法到达，但是这样时间复杂度很高。其实我们只要找最小的前缀和，找到最小的前缀和不就是最小的区间和吗？那么在一个区间中寻找最小值，就可以使用单调队列优化。
破环成链和前缀和

	for(int i = 1; i <= n; i++){
		cin>>p[i]>>d[i];
		p[n + i] = p[i];
		d[n + i] = d[i];
	}
	for(int i = 1; i <= 2 * n; i++) sum[i] = sum[i-1] + p[i] - d[i];

顺时针

顺时针，单调队列优化，滑动窗口做法。

	int head = 0, tail = 0;
	for(int i = 1; i < 2 * n; i++){
		while(head <= tail && i - q[head] >= n) head++;
		while(head <= tail && sum[q[tail]] >= sum[i]) tail--;
		q[++tail] = i;
		if(i >= n && sum[q[head]]-sum[i-n] >= 0) ans[i - n + 1] = 1;  //i为1的时候表示走向2，所以i为n的时候表示走向1
	}

因为是顺时针，所以当$i=n$的时候，表示回到原点。需要注意的是，第$i=n$的时候，表示走回加油站$1$。
$sum[q[head]]-sum[i-n]$计算的是区间和，如果最小的区间和大于等于$0$，那么其他区间和大于$0$,就符合到任意加油站，剩余油量都不为$0$，也就能返回起点。

逆时针

逆时针，可以先计算出后缀和，然后从后往前扫描，同时进行单调队列优化，大致差不多，细节需注意，毕竟方向反了，代码不可能一样。
后缀和计算方式，第$i$个点逆时针行驶，油量为$p[i]$，但距离不是$d[i]$，因为$d[i]$表示$i$去$i+1$，现在是$i$去$i-1$，所以距离在$d[i-1]$。
所以后缀和计算如下：

for(int i = 2 * n; i > 0; i--) sum[i] = sum[i + 1] + p[i] - d[i - 1];

反向扫描，单调队列优化，注意方向。

	head = 0, tail = 0;q[head] = 2 * n + 1; //初始化
	for(int i = 2 * n; i > 1; i--){
		while(head <= tail && q[head] - i >= n) head++; //如果不初始化，q[head]-i 就不能正确计算区间长度
		while(head <= tail && sum[q[tail]] >= sum[i]) tail--;
		q[++tail] = i;
		if(i <= n + 1 && sum[q[head]] >= sum[i + n]) ans[i - 1] = 1;
	}

当$i=n+1$的时候，就是要走向$n$，因为是逆时针，所以条件为$i\le n+1$ ，对应返回的位置$i-1$。
还要注意的是$head$要初始化为$2\ast n+1$，否则$q[head]-i\ge n$计算要出问题，即不初始化为$2\ast n-1$，会算出负数，显然是错误的。