专栏首页饶文津的专栏【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]

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
long long s[100005];//注意要开long long
int 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);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【CodeForces 717C】Potions Homework

    显而易见,最好的分配方法是最懒的人做最简单的任务,然后就排序求和。 注意用long long。

    饶文津
  • 【HDU 2874】Connections between cities(LCA)

    i和j在一棵树上,则最短路为dis[i]+dis[j]-dis[LCA(i,j)]*2。

    饶文津
  • 【HDU4947】GCD Array (莫比乌斯反演+树状数组)

    饶文津
  • P1850 换教室

    题目描述 对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。 在可以选择的课程中,有  节课程安排在 nn 个时间段上。在第  ...

    attack
  • 996扎心众生相:穷,就要拼命工作

    导读:最近程序员界发生了一件大事,有人在知名代码托管平台GitHub上发起了一个名为“996.ICU”的项目,以此抵制互联网公司的996工作制,立即得到大批程序...

    华章科技
  • stm32 HardFault_Handler调试及问题查找方法——飞思卡尔

    用户4645519
  • 跟我一起学docker(七)--网络

    IT故事会
  • 每日算法系列【LeetCode 523】连续的子数组和

    给定一个包含非负数的数组和一个目标整数 k,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,总和为 k 的倍数,即总和为 n*k,其中 n 也是...

    godweiyang
  • 交换输出

    输入n(n<100)个数,找出其中最小的数,将它与最前面的数交换后输出这些数。(如果这个第一个数就是最小的数,则保持原样输出,如果最小的数有相同的按照前面的交换...

    书童小二
  • JavaScript|数据类型的使用

    每一种计算机语言都有自己的数据结构和数据类型,JavaScript脚本语言中则是采用弱数据类型的方式,即一个数据不必首先做声明,可以在使用或赋值时再确定其数据的...

    算法与编程之美

扫码关注云+社区

领取腾讯云代金券