【hrbust2294】修建传送门

发布时间:2017-2-28 2:14:57 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【hrbust2294】修建传送门 ",主要涉及到【hrbust2294】修建传送门 方面的内容,对于【hrbust2294】修建传送门 感兴趣的同学可以参考一下。

题意

哈理工2016级新生程序设计全国邀请赛B题
n个点1~n,i到i+1的距离为a[i],现在可以在两个点之间建一个传送门,则两点之间距离为0,求建传送门后1号出发的最远距离最小是多少?

题解

a[i]的前缀和为s[i]。
假设在A、B两点建立传送门后,两点距离为dis[i][j]。

对于B固定的情况,最远距离要么是s[n-1]-s[B],要么是dis[1][k]里的最大值,k为A、B两点之间的点, dis[1][k]=min(s[k],s[A]+(s[B]-s[k]))。s[A]显然越小越好。所以就让A在第一个点的位置。于是dis[1][k]=min(s[k],s[B]-s[k])。

假设最大的dis[1][k]的 k 为 C。
满足\[s[j]<s[B]-s[j]且s[j+1]\ge s[B]-s[j+1]\]的 j 或者 j+1 就是 C(其实就是AB中间位置两边的点)。
这里的C是随着B递增不会减小的,因此不用O(\(n^2\)),只要每次维护 j 满足不等式即可。

代码

#include<cstdio>#include<algorithm>using namespace std;int n;long long s[100005];//注意要开long longint main(){    int t;    scanf("%d",&t);    while(t--){        scanf("%d",&n);        for(int i=1;i<n;i++){            long long a;            scanf("%lld",&a);            s[i]=s[i-1]+a;        }        int j=1;        long long ans=s[n-1];        for(int i=2;i<n;i++){            while(j<i&&s[j+1]<s[i]-s[j+1])j++;            ans=min(ans,max(max(s[j],s[i]-s[j+1]),s[n-1]-s[i]));        }        printf("%lld\n",ans);    }

上一篇:MySQL:Fabric 安装
下一篇:APP、网站、微信二次开发非常复杂的后台如何策划

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。