数组n个值切割成m段，保证m段中和值最小

[牛客网]shopee的零食柜

题目链接如下：/questionTerminal/24a1bb82b3784f86babec24e4a5c93e0?orderByHotValue=1&page=1&onlyReference=false

上代码

#include<iostream>#include<vector>using namespace std;void getMaxPacePerMinute(long n, long m, long bottom, long ceil, vector<long> &musics) {int maxPace = 0;while (bottom <= ceil) {maxPace = bottom + ((ceil - bottom) >> 1);//cout << "maxpace:" << maxPace <<" " <<bottom <<" " << ceil << endl;auto num = 0;for(auto i = 0; i < n;) {auto sum = 0;while(i < n && (sum + musics[i] <= maxPace)) {sum += musics[i++];}num++;if (num > m) {break;}}//cout << "m ,num:" << m << " " << num << endl;if (num <= m) {ceil = maxPace -1;} else {bottom = maxPace + 1;}}cout << maxPace << endl;return;}test/**8 56 5 6 7 6 6 3 1*/int main() {long n, m; //音符数，分钟数long bottom = 0, ceil = 0; //单分钟最小步数，最大步数cin >> n >> m;vector<long> musics(n, 0);for(auto i = 0; i < n; i++) {cin >> musics[i];bottom = max(bottom, musics[i]);ceil += musics[i];}//cout << n << m << bottom << ceil << endl;getMaxPacePerMinute(n, m, bottom, ceil, musics);return 0;}

分析：动态规划问题

其实是动态规划问题，看了调试你就知道怎么回事了Shopee git:(yinxiaolin) ✗ g++ -std=c++11 snackStand.cpp➜ Shopee git:(yinxiaolin) ✗ ./a.out8 56 5 6 7 6 6 3 1maxpace:23 7 40m ,num:5 2maxpace:14 7 22m ,num:5 4maxpace:10 7 13m ,num:5 6maxpace:12 11 13m ,num:5 5maxpace:11 11 11m ,num:5 511

如果觉得《数组n个值切割成m段 保证m段中和值最小》对你有帮助，请点赞、收藏，并留下你的观点哦！