1533: [POI2005]Lot-A Journey to Mars
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 174 Solved: 76
[Submit][Status]
Description
Byteazar 决定去火星参加一个空间站旅行. 火星的所有空间站都位于一个圆上. Byteazar 在其中一个登陆然后变开始饶圈旅行.
旅行需要耗费油料,一升油料只能跑1米,每个空间站可以补给的油料都有所不同. Byteazar
每到一个空间站便可以把该空间站的油料全部拿走.(他的油箱是没有容量限制的) 但是如果走到某个时候突然没油了那么旅行便失败了. Byteazar
需要决定要在哪个地方登陆使得他能顺利访问完所有的空间站后回到他当初登陆的地方. 一个细节是他登陆后可以选择两个方向中的任意一个进行旅行.
旅行需要耗费油料,一升油料只能跑1米,每个空间站可以补给的油料都有所不同. Byteazar
每到一个空间站便可以把该空间站的油料全部拿走.(他的油箱是没有容量限制的) 但是如果走到某个时候突然没油了那么旅行便失败了. Byteazar
需要决定要在哪个地方登陆使得他能顺利访问完所有的空间站后回到他当初登陆的地方. 一个细节是他登陆后可以选择两个方向中的任意一个进行旅行.
Input
第一行是一个数N (3 <= N <= 1
000 000). 表示空间站的总数. 空间站从1 到 N标号. 接下来N 行每行两个数pi 和 di (pi<= 0, di >
0). 表示第i个空间站所储存的油料以及第i个到第i + 1个空间站之间的距离( dN 表示第N个空间站到第1个空间站的距离).
所有的油料以及所有的距离的和保证不超过2 000 000 000.
000 000). 表示空间站的总数. 空间站从1 到 N标号. 接下来N 行每行两个数pi 和 di (pi<= 0, di >
0). 表示第i个空间站所储存的油料以及第i个到第i + 1个空间站之间的距离( dN 表示第N个空间站到第1个空间站的距离).
所有的油料以及所有的距离的和保证不超过2 000 000 000.
Output
输出n行,如果从第i个空间站登陆可以走遍所有的空间站那么打印TAK (YES is Polish), 否则打印NIE (NO in Polish).
Sample Input
5
3 1
1 2
5 2
0 1
5 4
3 1
1 2
5 2
0 1
5 4
Sample Output
TAK
NIE
TAK
NIE
TAK
NIE
TAK
NIE
TAK
HINT
Source
题解：
苦尽而后甘来。。。
如果总油量<总路程显然全部输出no
否则若总油量==总路程，构造前缀和s[i]=sigma(p[j]-d[j]) j<i 。
把(i,s[i])画在平面直角坐标系上，则选择最下方的一个点记为k开刀
因为从k出发，这条折线总是上升的，转一圈回到k，不会往下说明不会出现油量不够，所以该点可行。
继续将其推广 若总油量>总路程，则仍像上面一样构造一条折线。
记 res=sigma（p[i]-d[i])
则i 可行的充要条件是：
1）i 点 之后没有在 i 点 下方的点
2）i 点 之前点j满足 s[j]+res<s[i]
想一下如何转一圈就可以理解了
然后就可以前缀最小值乱搞了。。。
代码待UPD(我不会说我写了但是WA了）
发现了更简单的方法T_T
jcvb:(+p[i]-d[i])自复制一遍接在后面，求前缀和。然后能用单调队列搞出每个点往右走的最远距离，>=n则可行。逆时针同理再做一遍。
话说和我的做法差不多一样啊，只不过思考难度小一点。。。
UPD：单调队列做法 已A
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 2000000+100
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
struct rec{int x,y;}a[maxn];
int b[maxn],sta[maxn],r[maxn],res,n;
bool can[][maxn];
void work(int k)
{
b[]=;
for1(i,n)b[i]=b[i-]+a[i].x-a[i].y;
for1(i,n)b[n+i]=b[n+i-]+a[i].x-a[i].y;
int top=;b[*n+]=-inf;
for0(i,(n<<)+)
{
while(top&&b[i]<b[sta[top]])r[sta[top--]]=i-;
sta[++top]=i;
}
for0(i,n-)if(r[i]-i+>=n)can[k][i+]=;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();
for1(i,n)a[i].x=read(),a[i].y=read(),res+=a[i].x-a[i].y;
if(res<){for1(i,n)printf("NIE\n");return ;}
work();
for1(i,n>>)swap(a[i],a[n+-i]);
int t=a[].y;
for1(i,n-)a[i].y=a[i+].y;
a[n].y=t;
work();
for1(i,n)if(can[][i]||can[][n+-i])printf("TAK\n");else printf("NIE\n");
return ;
}我的做法 未A 不知为何 调了半天cena没调好 目测一些数据是对的
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 1000000+100
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
struct rec{int x,y;}a[maxn];
int b[maxn],c[maxn],res,n;
bool can[][maxn];
void work(int k)
{
for1(i,n)b[i]=b[i-]+a[i].x-a[i].y;
c[]=inf;can[k][]=;
for1(i,n-)
{
c[i]=min(c[i-],b[i]);
can[k][i+]=c[i]+res>=b[i]?:;
}
c[n]=inf;
for3(i,n-,)
{
c[i]=min(c[i+],b[i]);
if(can[k][i+])can[k][i+]=c[i]>=b[i]?:;
}
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();
for1(i,n)a[i].x=read(),a[i].y=read(),res+=a[i].x-a[i].y;
if(res<){for1(i,n)printf("NIE\n");return ;}
work();
for1(i,n>>)swap(a[i],a[n+-i]);
int t=a[].y;
for1(i,n-)a[i].y=a[i+].y;
a[n].y=t;
work();
for1(i,n)if(can[][i]||can[][n+-i])printf("TAK\n");else printf("NIE\n");
return ;
}发现错误是 逆时针转的时候必须把路的方向转过来，也就是 从 i 出发走的是 d[i-1] T_T
还有我的做法中只要一个条件不满足就不行。。。