首页 > 代码库 > shu_1078 vijos_1091(环城旅行)_单调队列

shu_1078 vijos_1091(环城旅行)_单调队列

http://202.121.199.212/JudgeOnline/problem.php?cid=1078&pid=9    


分析:  

               a[ i ] :  第i个城市的汽油与到下一个城市距离的差;

               dis[ i ] : 第i个城市到下一个城市的距离;

               s[ i ] : 前i个 a[ i ] 的和;  

               路径 i——》i+n 中间不断油,那么 T= ai + (ai+1)+ ...( ak)  对于任意的 i < k <=i+n, T都要大于0,

               即, T= s[ k ]- s[ i-1 ] >0 ;

               而只要所有的k中  min( s[ k ] ) > s[ i-1 ] 成立则满足条件,对于求区间的最值则利用单调队列。 

 

代码:

#include <stdio.h>
#include <string.h>
#define MAXN 1000004
 
int n,l;
int dis[MAXN],gas[MAXN];
int a[MAXN],s[MAXN];
int cnt,ans[MAXN/2];
 
struct node
{
    int s,no;
}q[MAXN];
 
void init()
{
    int sum=0;
    scanf("%d%d",&n,&l);
    scanf("%d%d",&dis[n],&gas[1]);
    for(int i=2;i<=n;i++){
        scanf("%d%d",&dis[i-1],&gas[i]);
        sum+=dis[i-1];
    }
    dis[n]=l-sum;
    for(int i=1;i<=n;i++)       a[i]=gas[i]-dis[i];
    for(int i=n+1;i<=2*n-1;i++) a[i]=a[i-n];
    s[0]=0;
    for(int i=1;i<=2*n-1;i++)   s[i]=s[i-1]+a[i];
}
 
void single_queue()
{
    int top=0,tail=0;
    for(int i=1;i<=n-1;i++){
        while(tail>top && q[tail].s>s[i]) tail--;
        q[++tail].s=s[i];
        q[tail].no=i;
    }
    for(int i=n;i<=2*n-1;i++){
        while(q[top].no<=i-n && top<tail) top++;
        while(tail>top && q[tail].s>s[i]) tail--;
        q[++tail].s=s[i];
        q[tail].no=i;
        if(s[i-n]<=q[top].s)  {ans[cnt++]=i-n+1;}
    }
}
 
int main()
{
    //freopen("in.txt","r",stdin);
 
    init();
    cnt=0;
    single_queue();
    if(cnt==0) printf("-1\n");
    else{
        for(int i=0;i<cnt-1;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[cnt-1]);
    }
    return 0;
}