14163: 【原4163】矮人的宝藏

题目描述

author: Yifan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4163

题目描述

矮人终于找到了他们失落的宝藏！现在有n个宝箱并排放在一起，第i个宝箱有\(a_i\)块黄金。m\(m \le n\)个矮人在讨论如何瓜分这些宝箱。规定每个矮人只能选择连在一起的若干个宝箱，每个宝箱都被一个矮人所拥有，每个矮人得到的黄金块数为他选择的所有宝箱的黄金块数之和。求获得黄金最多的矮人得到的黄金块数的最小值。

输入格式

第一行包含两个正整数n, m。

第二行包含n个用空格隔开的非负整数\(a_i\)（\(1 \le i \le n\)），保证\(a_i\)不全为0。

输出格式

一个正整数，表示获得黄金最多的矮人得到的黄金块数的最小值。

样例输入

5 3
4 2 4 5 1

样例输出

样例说明

第1个矮人选择第1个宝箱，得到4块黄金；第2个矮人选择第2，3个宝箱，得到6块黄金；第3个矮人选择第4，5个宝箱，得到6块黄金。获得黄金最多的矮人得到6块黄金。

数据范围

对20%的数据，\(n \le 10\)。

对50%的数据，\(n \le 1000\)。

对于100%的数据，\(n \le 100000, m \le n\)，\(a_i\)之和不超过\(10^9\)。

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

int val_data[100009] = { 0 };

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int left = 0, right = 0;

    for (int i = 0; i < n; ++i) {
        scanf("%d", &val_data[i]);
        right += val_data[i];
        left = val_data[i] > left ? val_data[i] : left;
    }

    int right_ans = 0;

    while (left <= right) {
        auto mid = (left + right) >> 1;
        int cnt = 0;
        for (int i = 0; i < n; ) {
            int cur_ans = 0;
            ++cnt;
            for (int j = i;; ++j) {
                cur_ans += val_data[j];
                if (cur_ans > mid) {
                    i = j;
                    break;
                }
                if (j == n - 1) {
                    i = j + 1;
                    break;
                }
            }
        }
        if (cnt <= m) {
            right_ans = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }

    cout << right_ans;

    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
int n,m,a[100001],l,r,mid,ans,cnt,cur;
bool flag;
int main() {
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;++i)
        scanf("%d",&a[i]);
    l=0;
    r=1000000000;
    while (l<=r){
        mid=(l+r)/2;
        cnt=0;
        cur=0;
        flag=true;
        for (int i=0;i<n;++i){
            if (a[i]>mid){
                flag=false;
                break;
            }
            if (cur+a[i]>mid){
                cur=0;
                cnt++;
            }
            if (cnt==m){
                flag=false;
                break;
            }
            cur+=a[i];
        }
        if (flag){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}

yyong119's solution

#include <cstdio>
#define MAX_N 100010
#define max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;
int n, m;
bool flag;
int a[MAX_N];
inline int read() {
    char ch = getchar(); int res = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}
int main() {
    n = read(), m = read();
    int l = 0, r = (int)1e9 + 5;
    for (register int i = 0; i < n; ++i) {
        a[i] = read();
        l = max(l, a[i]);
    }
    while (l < r) {
        int mid = (l + r) >> 1;
        flag = true;
        int cnt = 1, cur_sum = 0;
        for (register int i = 0; i < n; ++i)
            if (cur_sum + a[i] > mid) {
                cur_sum = a[i];
                ++cnt;
                if (cnt > m) {
                    flag = false; break;
                }
            }
            else cur_sum += a[i];
        if (flag) r = mid;
        else l = mid + 1;
    }
    printf("%d", l);
    return 0;
}