【POI补全计划#6 POI2005 LOT】
先考虑从1号点开始时如何判定能否绕一圈
发现只要对油量和路程的差求一下前缀和看一下2~n+1号空间站中有没有剩余油量小于0的位置(假设走到n+1号空间站自动瞬移到1号空间站)
又发现从第k个空间站出发相当于不管前面k-1个空间站,查询 k+1~n+1号空间站剩余油量 和 (1~k号空间站剩余油量 + n+1号空间站剩余油量) 是否有小于0的
这个信息可以通过一开始1号点出发的信息和k号空间站的前缀和处理出来,于是预处理一下从1号空间站开始时的那个前缀和的前缀min和后缀min就可以O(1)查询了
条件大概长这样
```cpp
mins[i+1]-delta>=0&&sum[n+1]-delta>=0&&sum[n+1]-delta+minp[i]>=0
```
(其中mins为前缀和的后缀min,minp为前缀和的前缀min,delta为第i个空间站的前缀和,sum[n+1]是所有油量总和减去所有路程总和)
最后反向处理一遍,判断沿编号减小方向走能不能回来就好了
~~不要忘了第i行的那个距离代表的是i~i+1间的距离,如果像我一样变换坐标算的话要重排一下距离~~
最后照例贴代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1000010;
int len[MAXN],fuel[MAXN],sum[MAXN],minp[MAXN],mins[MAXN],ans[MAXN];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&fuel[i],&len[i]);
memset(minp,0x7f,sizeof(minp));
memset(mins,0x7f,sizeof(mins));
for(int i=1;i<=n;++i)
{
sum[i+1]=sum[i]+fuel[i]-len[i];
if(minp[i]>sum[i+1])minp[i+1]=sum[i+1];
else minp[i+1]=minp[i];
}
for(int i=n+1;i>1;--i)
{
if(mins[i+1]>sum[i])mins[i]=sum[i];
else mins[i]=mins[i+1];
}
int delta;
for(int i=1;i<=n;++i)
{
delta=sum[i];
if(mins[i+1]-delta>=0&&sum[n+1]-delta>=0&&sum[n+1]-delta+minp[i]>=0)ans[i]|=1;
}
int tmp=len[n];
for(int i=n;i>=1;--i)
len[i]=len[i-1];
len[1]=tmp;
for(int i=1;i<n-i+1;++i)
{
swap(fuel[i],fuel[n-i+1]);
swap(len[i],len[n-i+1]);
}
memset(minp,0x7f,sizeof(minp));
memset(mins,0x7f,sizeof(mins));
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;++i)
{
sum[i+1]=sum[i]+fuel[i]-len[i];
if(minp[i]>sum[i+1])minp[i+1]=sum[i+1];
else minp[i+1]=minp[i];
}
for(int i=n+1;i>1;--i)
{
if(mins[i+1]>sum[i])mins[i]=sum[i];
else mins[i]=mins[i+1];
}
for(int i=1;i<=n;++i)
{
delta=sum[i];
if(mins[i+1]-delta>=0&&sum[n+1]-delta>=0&&sum[n+1]-delta+minp[i]>=0)ans[n-i+1]|=1;
}
for(int i=1;i<=n;++i)
{
if(ans[i])printf("TAK\n");
else printf("NIE\n");
}
return 0;
}
```
[email protected]
增加标题,增加部分详细描述