首页 > 代码库 > 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 (二分法,贪心)