AcWing 1088. 旅行问题（破环成链 + 单调队列优化）

一、问题

二、分析

我们先看下面的图
黑色代表两点之间消耗的油红色代表到达某个加油站可以获得的油。

我们发现每一个括号都是当前点获得的油减去到下一个点消耗的油。

因此我们可以将其存储在一个新的数组中。

那么对这个数组求前缀和就可以得到从A点到某点剩余的油如果剩余的油少于了0说明无法环游所有加油站。

所以我们需要保证上面的所有蓝色式子都是大于等于0的。

我们将其抽象在一个数轴上。

那么从某个点到某个点剩余的油可以表示为上图的样子。

我们发现从A到A的过程中我们需要让$s[1]$到$s[5]$减去$s[0]$的值都是大于等于$0$的因此我们只需要保证$s[1]$到$s[5]$中的最小值$s[i]$减去$s[0]$大于等于$0$。

接着想一下如何处理环我们在环形区间DP中对破环成链做过详细地介绍如果不太了解的话可以去看看
AcWing 1068. 环形石子合并环形区间DP

这里直接用结论将这个环拆开重复两遍即可。

而上图找最小值的过程又是我们的滑动窗口即单调队列。

如果不了解单调队列的话可以去看之前的算法专栏中的文章第九章单调栈与单调队列

题目中要求顺时针或者逆时针都能到环游顺时针这么做那么逆时针呢

我们可以将上面的图对称一下如下图所示

然后再做一次顺时针的操作即可但是要注意虽然单调队列的行为是一样的但是最后操作的编号要对称回去。比如我们最后对翻转后的进行顺时针操作时对2号标记而2号实际上是翻转前的7号。

三、代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
ll a[N], b[N], c[N], s[N], q[N];
int n, hh, tt = -1;
void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i ++ )
	{
		scanf("%d%d", a + i, b + i);
		c[i] = a[i] - b[i];
		a[i + n] = a[i];
		b[i + n] = b[i];
		c[i + n] = c[i];
	}
	
	for(int i = 1; i <= 2 * n; i ++ )
		s[i] = c[i] + s[i - 1];
	
	unordered_map<int, pair<bool, bool>>st;

	for(int i = 1; i <= 2 * n; i ++ )
	{
		if(hh <= tt && q[hh] < i - n + 1)hh ++;

		while(hh <= tt && s[q[tt]] >= s[i])tt --;
		
		q[++ tt] = i;
		
		if(i - n >= 0)
		{
			if(s[q[hh]] - s[i - n] >= 0)
				st[i - n + 1].first = true;
		}

	
	}
	
	for(int i= 1; i <= n / 2; i ++ )
	{
		swap(a[n - i + 1], a[i + 1]);
	}
	for(int i = 1; i <= n / 2; i ++ )
	{	
		swap(b[n - i + 1], b[i]);
	}
	
	for(int i = 1; i <= n; i ++ )
	 c[i] = c[i + n] = a[i] - b[i];
	
	for(int i = 1;i <= n * 2 ; i ++ ) 
		s[i]=s[i-1] + c[i];

	hh = 0, tt = - 1;
	for(int i = 1; i <= 2 * n; i ++ )
	{
		if(hh <= tt && q[hh] < i - n + 1)hh ++;

		while(hh <= tt && s[q[tt]] >= s[i])tt --;
		
		q[++ tt] = i;
		
		if(i - n >= 0)
		{
			int nums = i - n + 1;
			if(nums == 1)
			{
				if(s[q[hh]] - s[i - n] >= 0)
					st[i - n + 1].second = true;
			}
			else
			{
				int pos = n + 2 - nums;  
				if(s[q[hh]] - s[i - n] >= 0)
					st[pos].second = true;
			}

		}

		
	}
	for(int i = 1; i <= n; i ++ )
	{
		if(st[i].first || st[i].second)
			cout << "TAK" << endl;
		else cout << "NIE" << endl;
	}
}
int main()
{
	solve();
	return 0;
}