minimal sum

mail@pastecode.io avatar
unknown
plain_text
6 months ago
1.1 kB
2
Indexable
Never
#include <iostream>
using namespace std;
int minSumOfMaxSubset(int nums[], int n, int p) {
    int maxElement = nums[0];
    int sum = nums[0];

    for (int i = 1; i < n; i++) {
        maxElement = std::max(maxElement, nums[i]);
        sum += nums[i];
    }

    int left = maxElement;
    int right = sum;

    while (left < right) {
        int mid = (left + right) / 2;
        int count = 1;
        int currSum = 0;

        for (int i = 0; i < n; i++) {
            if (currSum + nums[i] > mid) {
                currSum = nums[i];
                count++;
            } else {
                currSum += nums[i];
            }
        }

        if (count > p) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

int main() {
	freopen ("input.txt","r",stdin);
    int n, p;
	cin >> p;
    cin >> n;
    int nums[1000];
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int minSum = minSumOfMaxSubset(nums, n, p);
	cout << "Case #" << minSum << endl;

    return 0;
}