bzoj1533: [POI2005]Lot-A Journey to Mars

传送门
如果总油量小于总里程显然gg
考虑维护前缀油量-里程
维护区间最小值。
如果最小值<头上的值显然gg
然后随便水水。

#include<cmath>
#include<cstdio> 
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 1000005
using namespace std;
struct data{int x,y;}a[N];
int b[N*2],c[2][N],sta[N*2],r[N*2];
int n,res,top;
void work(int x){
b[0]=0;
for (int i=1;i<=n;i++)
b[i]=b[i-1]+a[i].x-a[i].y;
for (int i=1;i<=n;i++)
b[n+i]=b[n+i-1]+a[i].x-a[i].y;
b[n*2+1]=-1e9; top=0;
for (int i=0;i<=n*2+1;i++){
while (top&&b[i]<b[sta[top]]){
r[sta[top]]=i-1;
top--;
}
sta[++top]=i;
}
for (int i=0;i<n;i++)
if (r[i]-i+1>=n) c[x][i+1]=1;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
res+=a[i].x-a[i].y;
}
if (res<0){
for (int i=1;i<=n;i++)
puts("NIE");
return 0;
}
work(0);
for (int i=1,j=n;i<j;i++,j--)
swap(a[i],a[j]);
int tmp=a[1].y;
for (int i=1;i<n;i++)
a[i].y=a[i+1].y;
a[n].y=tmp;
work(1);
for (int i=1;i<=n;i++)
if (c[0][i]||c[1][n-i+1])
puts("TAK");
else puts("NIE");
} 

最后

以上就是醉熏保温杯为你收集整理的bzoj1533: [POI2005]Lot-A Journey to Mars的全部内容，希望文章能够帮你解决bzoj1533: [POI2005]Lot-A Journey to Mars所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。