搬走要石

yinda_peng

资源限制
内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s
问题描述
　　住在有顶天的天人Tensi对自己的住处很不满。终于有一天她决定把门前碍眼的要石通通丢掉（怒扔要石）。控制要石自然是很容易的事，不过也会消耗灵力。假设搬走一块质量为1的要石会消耗1点灵力，而且由于要石都是连着放置的缘故所以每次除了搬走一颗，也可以搬走连续的任意数量的要石，自然质量是算在一起的。现在Tensi准备最多使用M次灵力，但是她太懒……所以每次只会使用同量的灵力， 也因为她太烂，所以也不愿意多花一点灵力……现在很懒的Tensi需要你帮她计算最少一次需要消耗多少灵力，能够在M次内把所有要石都丢到人间去……
输入格式
　　第一行两个数N,M，用一个空格分隔。1<=n<=1000,1<=m<=400
　　表示一共有N颗要石需要搬走已经Tensi最多发动M次灵力。
　　接下来包括N 个正整数 0<=ai<=40000 顺序表示每一颗要石的质量。
输出格式
　　输出一个数T
　　表示Tensi 每次至少消耗T灵力。0<=T<=1000000
　　如果无解输出-1.
样例输入
5 3
1 2 1 1 1
样例输出
3
数据规模和约定
　　对于100%的数据，1<=n<=1000，1<=m<=400，0<=ai<=40000。
　　保证0<=T<=1000000。

1. #include <stdio.h>
   
2. 
   
3. int check(int a[], int n, int m, int x) {
   
4.     int cnt = 0;
   
5.     int sum = 0;
   
6.     for (int i = 0; i < n; i++) {
   
7.         if (a[i] > x) {
   
8.             return 0;
   
9.         }
   
10.         if (sum + a[i] > x) {
    
11.             cnt++;
    
12.             sum = a[i];
    
13.         } else {
    
14.             sum += a[i];
    
15.         }
    
16.     }
    
17.     if (sum > 0) {
    
18.         cnt++;
    
19.     }
    
20.     return cnt <= m;
    
21. }
    
22. 
    
23. int main() {
    
24.     int n, m;
    
25.     scanf("%d %d", &n, &m);
    
26.     int a[n];
    
27.     int sum = 0;
    
28.     int max_num = 0;
    
29.     for (int i = 0; i < n; i++) {
    
30.         scanf("%d", &a[i]);
    
31.         sum += a[i];
    
32.         if (a[i] > max_num) {
    
33.             max_num = a[i];
    
34.         }
    
35.     }
    
36.    
    
37.     int left = max_num, right = sum;
    
38.     while (left < right) {
    
39.         int mid = left + (right - left) / 2;
    
40.         if (check(a, n, m, mid)) {
    
41.             right = mid;
    
42.         } else {
    
43.             left = mid + 1;
    
44.         }
    
45.     }
    
46.    
    
47.     printf("%d\n", left);
    
48.    
    
49.     return 0;
    
50. }

复制代码

当我们遇到需要在一个有序数组或者有序区间内查找某个特定值的问题时，可以考虑使用二分查找算法来提高效率。在这个问题中，我们需要找到最小的搬运质量，而质量是一个非负整数，并且单调，如果我们能够找到一个质量值x，使得给定的要石能够在m次搬运内搬走，并且不存在更小的质量值满足这个条件，那么x就是我们要找的答案。基于上述思路，我们可以使用二分查找来搜索符合条件的最小搬运质量。首先，我们确定搜索范围的左右边界。在这个问题中，质量的最小值是要石中最重的石头，而最大值是所有石头质量的总和。然后，我们在每次迭代中计算出中间值mid，检查是否存在一种分配方案使得最大质量不超过mid的情况下能够完成搬运任务。如果可以，说明我们可以尝试寻找更小的搬运质量，因此将搜索范围缩小为[left, mid]；如果不可以，说明当前的搬运质量太小，需要增大质量，因此将搜索范围缩小为[mid+1, right]。直到搜索范围缩小到只有一个元素，此时的元素就是最小的搬运质量。