网站建设寻找可以途径,wordpress 转移 问号,集团网站风格,广州专业的网站推广工具题意#xff1a;给出一个数列有n个数#xff0c;要求用分割分把这个数列分成m段#xff0c;不能改变原数列的顺序。每段至少一个数。求使得加和最大的那段的加和最小的划分方案。如果有多组解的话先要保证第一段和尽量小#xff0c;若仍有多组解#xff0c;要先保证第二段…题意给出一个数列有n个数要求用分割分把这个数列分成m段不能改变原数列的顺序。每段至少一个数。求使得加和最大的那段的加和最小的划分方案。如果有多组解的话先要保证第一段和尽量小若仍有多组解要先保证第二段和尽量小以此类推。 分析二分贪心。二分查找这个加和最大的段的加和最小值。在查找过程中每次枚举这个加和对数列从左到右看一遍看在每段加和不超过这个枚举值的前提下最少可以将这个数列分成几段。如果分段数小于等于m则这个枚举值偏大或者刚刚好如果大于m则说明枚举值偏小。 找到了这个值之后我们开始求最优方案我的做法是先保证最右面那段加和尽量大其次右数第二段加和尽量大以此类推。虽然与题中的左面最小的方案不同但是最终结果是一样的因为符合题目要求的那组解一定是左面最小最终一定会导致右面最大。对于这种右面最大的方式只需要从右到左将数列走一遍即可。注意处理保证右边最大之后划分的段数不足m的情况要做相应调整以满足每段至少一个数的要求。即将依次左面没有分隔符的空位画上分隔符。 #include iostream
#include cstdlib
#include cstring
#include cstdio
#include numeric
#include algorithm
using namespace std;#define MAX_BOOK_NUM 505int book_num, scriber_num;
long long book[MAX_BOOK_NUM];
bool cut_before[MAX_BOOK_NUM];void input()
{scanf(%d%d, book_num, scriber_num);for (int i 0; i book_num; i)scanf(%lld, book[i]);
}bool ok(long long a)
{long long temp 0;int cnt 1;for (int i 0; i book_num; i){if (temp book[i] a){temp book[i];continue;}temp book[i];cnt;if (cnt scriber_num)return false;}return cnt scriber_num;
}long long binary_search()
{long long l *max_element(book, book book_num);long long r accumulate(book, book book_num, 0);while (l r){long long mid (l r) / 2;if (ok(mid))r mid;elsel mid 1;}return l;
}void work()
{long long each binary_search();memset(cut_before, 0, sizeof(cut_before));long long temp 0;int cnt 0;for (int i book_num - 1; i 0; i--){if (temp book[i] each){temp book[i];continue;}cut_before[i 1] true;temp book[i];cnt;}int i 0;while (cnt scriber_num - 1){i;if (!cut_before[i]){cut_before[i] true;cnt;}}
}void output()
{printf(%lld, book[0]);for (int i 1; i book_num; i){if (cut_before[i])printf( /);printf( %lld, book[i]);}putchar(\n);
}int main()
{int t;scanf(%d, t);while (t--){input();work();output();}return 0;
} View Code 转载于:https://www.cnblogs.com/rainydays/archive/2013/06/12/3132717.html
