1331.Kick Veges' Ass SDNUOJ1331(简单二分)(2018总结赛)

Description
There are n veges stand in line, Albert_s plan to punish them since they are too weak. The picture following below shows one of the veges waiting to be kicked.

Now Albert_s plan to kick all the veges on days in order. Since Kick the vege costs him RP, and the final cost is equal to the max cost of one day on the days.

Albert_s wants to minimize the final cost, so how much RP he costs by following the rule above?

Input
The first line contains two integer ;

The second line contains space-separated integers , the elements of the array.



Output
A number indicating the answer.

Sample Input
5 2
2 1 3 4 5
Sample Output
9

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e5;

int n, k;
int a[N + 5];

bool judge(int rp)
{
    int cnt = 1;
    int sum = 0;
    for(int i = 0; i < n; ++i)
    {
        sum += a[i];
        if(sum > rp)
        {
            sum = a[i];
            cnt++;
        }
    }
    return cnt <= k;
}

int main()
{
    while(~scanf("%d%d", &n, &k))
    {
        int l = 0;
        int r = 0;
        for(int i = 0; i< n; ++i)
        {
            scanf("%d", &a[i]);
            l = max(l, a[i]);
            r += a[i];
        }
        while(l < r)
        {
            int mid = (r + l) / 2;
//            cout << judge(mid) << '\n';
            if(judge(mid))///如果中值可行,要找更小的值就把它作为右界(上限)
                r = mid;
            else
                l = mid + 1;
        }
        cout << r << '\n';
    }
    return 0;
}

全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 11:27
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务