Advertisement
Guest User

Untitled

a guest
Jul 27th, 2017
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.45 KB | None | 0 0
  1. //UVA714CopyingBooks
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7.  
  8. const int MAXN = 500 + 10;
  9. int n, k, N;
  10. int p[MAXN];
  11. int solve(int ans) {
  12. long long done = 0, part = 1;
  13. for(int i = 0; i < n; i++) {
  14. if(done + p[i] <= ans) done += p[i];
  15. else {
  16. done = p[i]; part++;
  17. }
  18. }
  19. return part;
  20. }
  21. void print(long long ans) {
  22. //printf("ans = %d\n", ans);
  23. int slash[MAXN] = {0};
  24. long long done = 0, left = k - 1;//left标记剩余的斜杠数
  25. for(int i = n - 1; i >= 0; i--) {//反向来,同样是贪心
  26. if(done + p[i] <= ans) done += p[i];
  27. else {
  28. slash[i] = 1; done = p[i]; left--; //标记分隔号的位置,在当前元素前面,便于打印,更新累加器done
  29. }
  30. }
  31. for(int i = 0; i < n && left; i++)
  32. if(!slash[i]) {
  33. left--; slash[i] = 1;
  34. }
  35. for(int i = 0; i < n - 1; i++) {
  36. printf("%d ", p[i]);
  37. if(slash[i]) printf("/ ");
  38. }
  39. printf("%d\n", p[n - 1]);
  40. }
  41. int main() {
  42. //freopen("UVA714out.txt", "w", stdout);
  43. scanf("%d", &N);
  44. while(N--) {
  45. int maxd = 0;
  46. long long tot = 0;
  47. scanf("%d%d", &n, &k);
  48. for(int i = 0; i < n; i++) {
  49. scanf("%d", &p[i]);
  50. maxd = max(maxd, p[i]);
  51. tot += p[i];
  52. }
  53. long long L = maxd, R = tot;
  54. while(L < R) {//二分子序列总和的上界
  55. long long M = L + (R - L) / 2;
  56. if(solve(M) <= k) R = M;
  57. else L = M + 1;
  58. }
  59. print(L);
  60. }
  61.  
  62. return 0;
  63. }
  64. /*
  65. 2
  66. 9 3
  67. 100 200 300 400 500 600 700 800 900
  68. 5 4
  69. 100 100 100 100 100
  70. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement