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