[题目描述] :
John 打算驾驶一辆汽车周游一个环形公路. 公路上总共有 n 个车站, 每个站都有若干升汽油 (有的站可能油量为零), 每升油可以让汽车行驶一千米.
John 必须从某个车站出发, 一直按顺时针 (或逆时针) 方向走遍所有的车站, 并回到起点. 在一开始的时候, 汽车内油量为零, John 每到一个车站就把该站所有的油都带上 (起点站亦是如此), 行驶过程中不能出现没有油的情况.
任务: 判断以每个车站为起点能否按条件成功周游一周.
[输入描述] :
第一行是一个整数 n, 表示环形公路上的车站数;
接下来 n 行, 每行两个整数 pi,di 分别表示表示第 i 号车站的存油量和第 i 号车站到下一站的距离.
[输出描述] :
输出共 n 行, 如果从第 i 号车站出发, 一直按顺时针 (或逆时针) 方向行驶, 能够成功周游一圈, 则在第 i 行输出 TAK, 否则输出 NIE.
[样例输入] :
- 5
- 3 1
- 1 2
- 5 2
- 0 1
- 5 4
[样例输出] :
- TAK
- NIE
- TAK
- NIE
- TAK
[时间限制, 数据范围及描述] :
时间: 2s 空间: 512M
30% 的数据: 3<=n<=10^4;
70% 的数据: 3<=n<=10^5;
100% 的数据: 3<=n<=10^6;0<=pi<=2*10^9;0<di<=2*10^9;
本题的暴力做法是将数组拓宽 2 倍, 对其做一遍前缀和, 每次对长度为 n 的序列进行区间减法, 减去前一位数, 即得到此长度为 n 的序列的前缀和,
然后看其中最小的是否 >=0, 一共做 n 次, 然后统计答案即可.(这里的区间减法可以直接简化成求区间最小, 然后判断其是否 >= 前一位数)
正解做法即用单调队列维护区间最小的数即可.
注意: 每个站到下一个站的距离是顺时针给出的.
- Code:
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- const int N=2000005;
- long long sum[N];
- int n,p[N],d[N],ok[N],Q[N];
- void DP1(){
- int head=1,tail=0;
- for(int i=1;i<=n;i++){
- while(head<=tail&&sum[Q[tail]]>=sum[i]){
- --tail;
- }
- Q[++tail]=i;
- }
- for(int i=n+1;i<=2*n;i++){
- while(head<=tail&&sum[Q[tail]]>=sum[i]){
- --tail;
- }
- Q[++tail]=i;
- while(head<=tail&&Q[head]<=i-n-1){
- ++head;
- }
- if(sum[Q[head]]>=sum[i-n-1]){
- ok[i-n]=1;
- }
- }
- }
- void DP2(){
- int head=1,tail=0;
- for(int i=n*2;i>=n+1;i--){
- while(head<=tail&&sum[Q[tail]]>=sum[i]){
- --tail;
- }
- Q[++tail]=i;
- }
- for(int i=n;i>=1;i--){
- while(head<=tail&&sum[Q[tail]]>=sum[i]){
- --tail;
- }
- Q[++tail]=i;
- while(head<=tail&&Q[head]>=i+n){
- ++head;
- }
- if(sum[Q[head]]>=sum[i+n]){
- ok[i]=1;
- }
- }
- }
- int main(){
- scanf("%d",&n);
- for(int i=1;i<=n;i++){
- scanf("%d%d",&p[i],&d[i]);
- p[i+n]=p[i];
- d[i+n]=d[i];
- sum[i]=sum[i-1]+p[i]-d[i];
- }
- for(int i=n+1;i<=n*2;i++){
- sum[i]=sum[i-1]+p[i]-d[i];
- }
- DP1();
- for(int i=n*2;i>=1;i--){
- sum[i]=sum[i+1]+p[i+1]-d[i];
- }
- DP2();
- for(int i=1;i<=n;i++){
- if(ok[i]){
- printf("TAK\n");
- }
- else{
- printf("NIE\n");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3201326.html