思路
1.顺时针
for循环从前往后版本可以看第二版代码
2.逆时针
因为思路大致相同,所以在此略写
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
long long s[N*2];//前缀和
int q[N*2],o[N],d[N],mark[N];
//o[i]表示到i地点所需要的油,d[i]表示i到i+1消耗的油,mark[i]等于1时表示能环球旅行,0时不能
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&o[i],&d[i]);
//计算前缀和
for(int i=1;i<=n;i++) s[i]=s[i+n]=o[i]-d[i];//表示i地点加的油和到下一地点消耗的油的差
for(int i=1;i<=2*n;i++) s[i]+=s[i-1];
int hh=0,tt=-1;
/*
从大到小遍历的原因:
比如计算到i=6这个点时,需要的数据是6~13这个区间内的的前缀和,
如果从小到大遍历,那么队列中并不会存在6~13这个区间内的前缀和,
所以要从大到小进行枚举遍历
*/
for(int i=2*n;i>=1;i--)
{
if(hh<=tt&&q[hh]>i+n-1) hh++;//窗口范围为n
while(hh<=tt&&s[q[tt]]>=s[i]) tt--;//保持单调递增,q中大于s[i]的都出队
q[++tt]=i;//s[i]入队
if(i<=n&&s[q[hh]]>=s[i-1]) mark[i]=1;//最小值大于,那么可以环球旅行
}
//逆时针顺序
hh=0,tt=-1;
d[0]=d[n];//s[1]计算的时候需要
for(int i=1;i<=n;i++) s[i]=s[i+n]=o[i]-d[i-1];
for(int i=2*n;i>=0;i--) s[i]+=s[i+1];//因为为逆时针,所以s数组从后往前看
for(int i=1;i<=2*n;i++)
{
if(hh<=tt&&q[hh]<i-n+1) hh++;//范围在n之内
while(hh<=tt&&s[q[tt]]>=s[i]) tt--;//保持单调递增,q中大于s[i]的都出队
q[++tt]=i;//s[i]进队
if(i>n&&s[q[hh]]>=s[i+1]) mark[i-n]=1;//因为单调递减性,n范围内s[q[hh]]为最小值.
}
for(int i=1;i<=n;i++)
if(mark[i]) printf("TAK\n");
else printf("NIE\n");
return 0;
}
for循环从前往后的版本
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
long long s[N*2];
int q[N*2],o[N],d[N],mark[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&o[i],&d[i]);
for(int i=1;i<=n;i++) s[i]=s[i+n]=o[i]-d[i];
for(int i=1;i<=2*n;i++) s[i]+=s[i-1];
int hh=0,tt=-1;
for(int i=1;i<=2*n;i++)
{
if(hh<=tt&&q[hh]<i-n) hh++;//因为q里面应该要包括i,所以q[hh]可以等于i-n,但不能小于
while(hh<=tt&&s[q[tt]]>=s[i]) tt--;
q[++tt]=i;
if(i>=n&&s[q[hh]]>=s[i-1-n]) mark[i-n]=1;
}
hh=0,tt=-1;
d[0]=d[n];
for(int i=1;i<=n;i++) s[i]=s[i+n]=o[i]-d[i-1];
for(int i=2*n;i>=0;i--) s[i]+=s[i+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&&s[q[hh]]>=s[i+1]) mark[i-n]=1;
}
for(int i=1;i<=n;i++)
if(mark[i]) printf("TAK\n");
else printf("NIE\n");
return 0;
}
到这看懂了 感谢~~
边界条件判断有问题啊!!!
从先到后顺时针写法的:
while(hh<=tt&&s[q[tt]]>=s[i]) tt–;
q[++tt]=i;
if(i>=n&&s[q[hh]]>=s[i-1-n]) mark[i-n]=1;
是不是顺序写反了,应该先判断再更新吧
tql!!Orz
楼主,for循环从前往后的代码里顺时针部分
这里为什么是>=s[i - 1 - n] 而不是s[i - n]呀
1~n,n+1~2n,是这样的排列规矩吧,时代有点久远我也记得不太清楚啦
应该跟上方保持一致吧
好吧感觉顺序总是搞不太明白orz
楼主还记得for循环从前往后和从后往前的区别吗,我看y总在代码里说
但看了还是感觉理解不过来= =
感觉应该就是s[i - n];不然按照魔女巨巨的代码,i==n –> i-1-n为-1,就会出现边界问题
我这个写的是
s[i - n]
。https://www.acwing.com/activity/content/code/content/2626794/
楼主,你题解里写错了吧?怎么一会w, 一会s的?
emmm好像写错了,注意一下就行了hh
有时间会改的
我终于看明白了,写得不错,谢谢^_^
while(hh<=tt&&s[q[tt]]>=s[i]) tt–;//保持单调递减单调性,q中大于s[i]的都出队
应该是保持单调递增吧
谢谢指正
貌似下面逆时针的也是