首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。