首页 > 代码库 > BZOJ1533: [POI2005]Lot-A Journey to Mars
BZOJ1533: [POI2005]Lot-A Journey to Mars
1533: [POI2005]Lot-A Journey to Mars
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 174 Solved: 76
[Submit][Status]
Description
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.
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了）
BZOJ1533: [POI2005]Lot-A Journey to Mars
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。