Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //UVA714CopyingBooks
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int MAXN = 500 + 10;
- int n, k, N;
- int p[MAXN];
- int solve(int ans) {
- long long done = 0, part = 1;
- for(int i = 0; i < n; i++) {
- if(done + p[i] <= ans) done += p[i];
- else {
- done = p[i]; part++;
- }
- }
- return part;
- }
- void print(long long ans) {
- //printf("ans = %d\n", ans);
- int slash[MAXN] = {0};
- long long done = 0, left = k - 1;//left标记剩余的斜杠数
- for(int i = n - 1; i >= 0; i--) {//反向来,同样是贪心
- if(done + p[i] <= ans) done += p[i];
- else {
- slash[i] = 1; done = p[i]; left--; //标记分隔号的位置,在当前元素前面,便于打印,更新累加器done
- }
- }
- for(int i = 0; i < n && left; i++)
- if(!slash[i]) {
- left--; slash[i] = 1;
- }
- for(int i = 0; i < n - 1; i++) {
- printf("%d ", p[i]);
- if(slash[i]) printf("/ ");
- }
- printf("%d\n", p[n - 1]);
- }
- int main() {
- //freopen("UVA714out.txt", "w", stdout);
- scanf("%d", &N);
- while(N--) {
- int maxd = 0;
- long long tot = 0;
- scanf("%d%d", &n, &k);
- for(int i = 0; i < n; i++) {
- scanf("%d", &p[i]);
- maxd = max(maxd, p[i]);
- tot += p[i];
- }
- long long L = maxd, R = tot;
- while(L < R) {//二分子序列总和的上界
- long long M = L + (R - L) / 2;
- if(solve(M) <= k) R = M;
- else L = M + 1;
- }
- print(L);
- }
- return 0;
- }
- /*
- 2
- 9 3
- 100 200 300 400 500 600 700 800 900
- 5 4
- 100 100 100 100 100
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement