[Acwing] 1088. 旅行问题 单调队列问题

前言

传送门 :

思路

我们考虑 a [ i ] = o i l [ i ] − d i s t [ i ] a[i] = oil[i] -dist[i] a[i]=oil[i]−dist[i]也就是如果从当前点顺时针走,需要消耗多少油,在考虑邮箱是空的情况下

我们对 a [ i ] a[i] a[i]求一个前缀和,因此问题合法化就转化为 s u m [ i ] − s u m [ j ] > 0 sum[i]-sum[j]>0 sum[i]−sum[j]>0

我们通过移动 s u m [ i ] > s u m [ j ] sum[i]>sum[j] sum[i]>sum[j],因此我们考虑对于经过的车站中 s u m [ j ] m i n 是 否 小 于 s u m [ i ] sum[j]_{min}是否小于 sum[i] sum[j]min​是否小于sum[i],因此就变成了一个单调队列问题

MYcode

void solve()
{
	cin>>n;
	for(int i=1;i>oil[i]>>dist[i];
		s[i] = s[i+n] = oil[i] - dist[i];
	}
	
	for(int i=1;i= 1;i --)
        {
            //起点为i的情况下，最长路径的为n,所以超过i + n就是不合法的
            if(hh  i + n - 1) hh ++;

            while(hh = s[i]) tt --;
            q[++ tt] = i;

            //计算顺时针(因为s[i]固定，所以要求最小的s[q[hh]]（s[j]），因为如果最小的s[j] - s[i]都符合要求，那么剩下的的也一定符合要求)
            if(i = 0) ans[i] = true;
            //因为j的范围是i = 1;i --) s[i] += s[i + 1];
        hh = 0,tt = -1;
        for(int i = 1;i