工资

题目描述

聪哥在暑假参加了打零工的活动, 这个活动分为 n 个工作日, 每个工作日的工资为 Vi. 有 m 个结算工钱的时间, 聪哥可以自由安排这些时间, 也就是说什么时候拿钱, 老板说的不算, 聪哥 才有发言权! (因为聪哥是土豪, 他是老板的老板)

聪哥不喜欢身上一次性有太多的钱, 于是他想安排一下拿钱的时间, 使他一次性拿的钱中最大的最小. (最后一天一定要领钱)

输入格式

第一行 2 个数 n, m

接下来 n 行, 每行一个数, 代表 Vi.

输出格式

最小的最大钱数.

样例输入

7 5
100
400
300
100
500
101
400

样例输出

500

样例说明

100 400 // 300 100 // 500 // 101 // 400 //

“//” 表示老大要去拿钱.

数据范围

20%\(1 \leq n \leq 20\)

另 20%\(1 \leq n \leq 50\),\(V_i\) 的和不超过 1000

100%\(1 \leq n \leq 100000, m \leq n, V_i \leq 10000\)

Explanation

也就是二分答案等等~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 100100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

int n, m;
lli arr[maxn];

// Whether the max limit 'size' would be appreciable, id est,
// can you take it according to the rules.
bool judge(lli size)
{
    int did = 0, // How many times taken
        last_take = 0;
    lli sum = 0; // Gathered money already
    for (int i = 1; i <= n + 1; i++) {
        if (sum + arr[i] > size) {
            // Commit changes
            did += 1;
            sum = arr[i];
            last_take = i;
        } else {
            sum += arr[i];
        }
    }
    if (last_take < n)
        did += 1;
    if (did > m)
        return false;
    return true;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    // Binary search with maximum values.
    lli v_sum = 0, v_max = 0;
    for (int i = 1; i <= n; i++) {
        v_sum += arr[i];
        v_max = max(v_max, arr[i]);
    }
    lli left = v_max, mid, right = v_sum;
    while (left < right) {
        mid = (left + right) >> 1;
        if (judge(mid))
            right = mid - 1;
        else
            left = mid + 1;
    }
    if (judge(left))
        printf("%lld\n", left);
    else
        printf("%lld\n", left + 1);
    return 0;
}