首页 > 代码库 > UVa714 Copying Books (二分法,贪心)
UVa714 Copying Books (二分法,贪心)
链接:http://vjudge.net/problem/UVA-714
分析:二分枚举最小值,用贪心的思想每段序列尽量往右划分,注意:因为要求字典序最小解,输出时还有一个贪心过程,左起S[i]尽量小,相当于右起S[j]尽量大,还有一种情况是剩下的数之和已经小于等于ans,但是此时剩余要分配的组数还有多(remain>1)。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 const int maxm = 500 + 5; 7 8 int m, k, p[maxm]; 9 10 int solve(long long maxp) {11 int ans = 1;12 long long done = 0;13 for (int i = 0; i < m; i++) {14 if (done + p[i] <= maxp) done += p[i];15 else { done = p[i]; ans++; }16 }17 return ans;18 }19 20 int last[maxm];21 void print(long long ans) {22 long long done = 0;23 int remain = k;24 memset(last, 0, sizeof(last));25 for (int i = m - 1; i >= 0; i--) {26 if (done + p[i] > ans || i + 1 < remain) {27 last[i] = 1; remain--; done = p[i];28 } else done += p[i];29 }30 for (int i = 0; i < m-1; i++) {31 printf("%d ", p[i]);32 if (last[i]) printf("/ ");33 }34 printf("%d\n", p[m-1]);35 }36 37 int main() {38 int T;39 scanf("%d", &T);40 while (T--) {41 scanf("%d%d", &m, &k);42 long long tot = 0;43 int maxp = -1;44 for (int i = 0; i < m; i++) {45 scanf("%d", &p[i]);46 tot += p[i];47 maxp = max(maxp, p[i]);48 }49 long long L = maxp, R = tot;50 while (L < R) {51 long long M = L + (R-L)/2;52 if (solve(M) <= k) R = M;53 else L = M+1;54 }55 print(L);56 }57 return 0;58 }
UVa714 Copying Books (二分法,贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。