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;
}

全部评论

相关推荐

06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
07-15 12:24
重庆大学 运营
坏消息:和好工作擦肩而过
给点吧求求了:怎么可能因为差几秒,估计就是简历更好看婉拒了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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