题意
John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 $n$ 车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。在一开始的时候,汽车内油量为零,John 每到一个车站就把该站所有的油都带上(起点站亦是如此),行驶过程中不能出现没有油的情况。 任务:判断以每个车站为起点能否按条件成功周游一周。 可以输出TAK否则输出NIE思路
先考虑顺时针 设$a_i$表示从$i$站到下一站,车内的汽油增加(减少)了多少。 设$sum_i$表示$a_i$的前缀和,那么如果要判断从某个车站出发是否能周游一周其实就是判断$sum_i-sum_{i-1},sum_{i+1}-sum_{i-1} \dots sum_{i+n-1}-sum_{i-1}$是否有负数,也就是$sum_i,sum_{i+1} \dots sum_{i+n-1}$ 的最小值减去$sum_{i-1}$是否为负数,我们知道,求最小值可以使用RMQ算法(当然线段树也可以),所以使用RMQ+ST表就可以做出顺时针是否可以绕一圈了。 至此,你已经得到了20分。 再考虑逆时针,与顺时针刚好相反。部分量需要变化。 比如逆时针判断$sum_i,sum_{i+1} \dots sum_{i+n-1}$ 的最小值减去$sum_{i-1}$是否为负数时,如果为负数则代表$i+n-1$不行,而不是$i$。 逆时针的初始也要更新,与顺时针不同:
1 2 3 4 |
memcpy(tmp,p,sizeof(p)); for(ll i=1;i<=n;i++) p[i]=tmp[n-i+1]; memcpy(tmp,d,sizeof(d)); for(ll i=1;i<=n;i++) d[i]=tmp[n-i];d[n]=tmp[n]; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #define ll long long using namespace std; inline ll read(){ ll res=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f; } inline void write(ll x){ if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else{ write(x/10); putchar(x%10+'0'); } } ll n,ans[2000010],a[2000010],tmp[2000010]; ll p[2000010],d[2000010],sum[2000010],f[2000010][20]; void ST(){ for(ll j=1;(1<<j)<=n*2;j++){ for(ll i=1;i+(1<<j)-1<=n*2;i++){ f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } } ll RMQ(ll l,ll r){ ll k=0; while((1<<(k+1))<=r-l+1) k++; return min(f[l][k],f[r-(1<<k)+1][k]); } int main(){ n=read(); for(ll i=1;i<=n;i++) p[i]=read(),d[i]=read(); //顺时针 sum[0]=0; memset(f,63,sizeof(f)); for(ll i=1;i<=n*2;i++){ sum[i]=sum[i-1]+(p[i]-d[i]); } for(ll i=1;i<=n*2;i++){ f[i][0]=sum[i]; } ST(); for(ll i=1;i<=n;i++){ ll qx=RMQ(i,i+n-1); if(qx>=sum[i-1]) ans[i]=1; } //逆时针 memcpy(tmp,p,sizeof(p)); for(ll i=1;i<=n;i++) p[i]=tmp[n-i+1]; memcpy(tmp,d,sizeof(d)); for(ll i=1;i<=n;i++) d[i]=tmp[n-i];d[n]=tmp[n]; sum[0]=0; memset(f,63,sizeof(f)); for(ll i=1;i<=n*2;i++){ sum[i]=sum[i-1]+(p[i]-d[i]); } for(ll i=1;i<=n*2;i++){ f[i][0]=sum[i]; } ST(); for(ll i=1;i<=n;i++){ ll qx=RMQ(i,i+n-1); if(qx>=sum[i-1]) ans[n-i+1]=1; } for(ll i=1;i<=n;i++){ if(ans[i]==1) puts("TAK"); else puts("NIE"); } return 0; } |