n很小,直接爆搜+剪枝
class Solution {
public:
int n, k;
vector<int> sum;
int ans = INT_MAX;
void dfs(vector<int>& jobs, int u, int group){
int h = *max_element(sum.begin(), sum.end());
if (h >= ans) return;
if (u == n){
ans = h;
return;
}
for (int i = 0; i<group; i++){
sum[i] += jobs[u];
dfs(jobs, u + 1, group);
sum[i] -= jobs[u];
}
if (group >= k) return;
sum[group] += jobs[u];
dfs(jobs, u + 1, group + 1);
sum[group] -= jobs[u];
}
int minimumTimeRequired(vector<int>& jobs, int _k) {
n = jobs.size(), k = _k;
sum.resize(k, 0);
sort(jobs.begin(), jobs.end()); reverse(jobs.begin(), jobs.end());
dfs(jobs, 0, 0);
return ans;
}
};