题目
分配最小页数 （学校OJ 357题）
给定n本书的页数，m名学生。这些书按页数的升序排列成一个序列。每个学生都被分
配去读一些序列中连续的书。设分配给第i个学生的书籍的总页数为Pi，1<=i<=m。找出
优化的分配方式，使得最大的Pi最小。用分治法求解。
输入描述
第一行输入t，表示t个测试用例
对于每一个测试用例第一行输入n和m，表示书的数量和学生的数量
第二行按升序输入n个整数，表示书的页数。
输出描述
t行，表示t个测试用例的解
样例输入
2
4 2
12 34 6790
15 7
12 34 67 90 95 103 150 165 170 198 201 235 240 245 251
样例输出
113
436
问题分析与算法设计思路
思路1：类似枚举的分治（暴力）
基本思路：我们这样划分问题，不妨使第一个同学看书 x 页；而剩余的书和同学则构成一个原问题的子问题，使剩余同学中看书最多的同学看了 y 页。那么所有同学中的最大页数z = m a x ( x , y ) z = max(x,y)z=max(x,y)。
而对于剩余的书和同学，我们继续划分为一个同学和其它剩余的同学。直到只剩下一个同学时，就不可再分，组合这些子问题的解将得到最初原问题的解。
思路2：二分法
在思路1中，我们以同学为主要对象进行，通过改变给同学分配的书的数量，来搜索解空间。
基本思路：这里对问题引入一种新的描述，以方便理解。我们把每个同学看作一个桶，而每本书看作一个物品，书的页数就是物品的大小。每个桶有一个最大容量，分配书籍就是将物品一个个放入桶中，当一个桶放不下时，就将物品放到下一个桶中。那么问题就变成了，要找一个最小桶容量，而恰好能将所有的物品都放进桶中。
因此，这里问题的主要对象是桶的容量。
算法过程：对桶容量进行二分搜索，找到最小桶容量。
首先确定一个桶容量的大致范围。不妨令第 i 个物品的大小为 a [ i ] a[i]a[i]，所有物品大小和为 sum，则桶容量的初始区间为 [ a [ m ] , s u m ] [a[m],sum][a[m],sum]（m 为物品数量）。
搜索：
设初始搜索区间为 [ f i r s t , e n d ] [first,end][first,end]
先取中间值 m i d = ( f i r s t + e n d ) / 2 mid=(first+end)/2mid=(first+end)/2，然后对容量 mid 进行判断
恰好合适，可以放下所有物品，但桶容量再减小 1 就放不下了。
桶小了，放不下所有物品，则搜索区间的右边 [ m i d + 1 , e n d ] [mid+1,end][mid+1,end]
桶大了，能放下所有物品，但不是恰好合适，则搜索区间左边 [ f i s r t , m i d − 1 ] [fisrt,mid-1][fisrt,mid−1]。
递归求解。
判断桶能否放下所有物品：
遍历物品序列，逐个放入桶中。若需要桶的数量大于 m，则桶容量小了。
算法实现（C++）
思路1实现
#include<iostream> using namespace std; const int Big = 8848;//用作极大值 int renshu;//学生人数 int anser(int m,int n,int l,int r,int a[])//表示m堆书，n个学生在分摊之后，返回学生所看书的最大页数 { // cout<<"m="<<m<<" n="<<n<<" l="<<l<<endl; int answer = 0; if(n == 1) { int sum = 0; for(int i = l; i <= r; i++) { sum += a[i]; } answer = sum; goto label; } if(m == n) { answer = a[r]; goto label; } if(m < n) { answer = Big; goto label; } if(m > n) { int minOfMax = Big; int sum = 0; for(int i = l; i <= m - n + l; i++) { // cout<<"-------------------i="<<i<<" m-n+l= "<<m-n+l<<endl; sum += a[i]; int t = anser(m-i+l-1, n-1, i+1, r, a); int maxNum = max(sum, t);//原问题分成两部分，取最大值 if(maxNum == 13) { system("pause"); } minOfMax = min(minOfMax, maxNum); } answer = minOfMax; } label: return answer; } int main() { int t,m,n; cin>>t;//t表示测试案例数 for(int j=0;j<t;j++) { cin>>m>>n;//m表示书堆的数目，n表示学生数目 renshu=n; int *a=new int[m+1]; for(int i=0;i<m;i++) cin>>a[i]; int answer = anser(m,n,0,m-1,a);//递归求解 cout<<"answer: "<<answer<<endl; delete [] a; } return 0; } /*测试数据 2 4 2 12 34 67 90 15 7 12 34 67 90 95 103 150 165 170 198 201 235 240 245 251 */
思路2实现
运行
代码
为了方便展示运行效果，代码中嵌入了一些输出中间变量值的语句。而且在 main 函数中仅安排了一个测试用例的输入。
#include<iostream> using namespace std; int TwoPointSearch(int f, int e, int a[], int n, int m); bool Can(int a[], int n, int x, int m); int main(){ int n = 0;//物品数量 int m = 0;//桶的数量 int sum = 0;//物品大小之和 cin >> n >> m; int *a = new int[n]; for(int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } int answer = TwoPointSearch(a[n-1], sum, a, n, m); cout<<"answer:"<<answer<<endl; return 0; } int TwoPointSearch(int f, int e, int a[], int n, int m) { //返回：能装下的最小桶容量 cout << "arange:" << f << " " << e; int mid = (f + e) / 2; bool can = Can(a, n, mid, m); cout << " can:" << can; cout << " mid:" << mid << endl; if(can) { int can_smaller = Can(a, n, mid-1, m); if(! can_smaller) { return mid; } else { return TwoPointSearch(f, mid-1, a, n, m); } } else { return TwoPointSearch(mid+1, e, a, n, m); } } bool Can(int a[], int n, int x, int m) { //放得下吗？ //n:物品数，m:桶数 int flag = false; //to test if(x < a[0]) { return false; } int need = 0;//需要桶的数量 int sum = 0;//一个桶已经装了多少 for(int i = 0; i < n; i++) { if(sum + a[i] <= x) { sum += a[i]; } else { sum = a[i]; need++; } if(need + 1 > m) { return false; } } return true; }
bug记录
1、子问题对最大值没有实现最小化
问题分析
answer这个全局变量很不好，破坏了递归的逻辑。
本来要分治，前面一部分就是k，然后后面是剩余部分的最小化最大值。
代码里是用什么实现最大值的最小化的？就是answer，但answer之会在递归的第一层更新。
也就是说，对分治后的后面一段子数组，并没有实现最大值的最小化。
解决方案（见思路1实现）
改用将 answer 作为函数内的局部变量的写法。
问题代码版本
#include<iostream> using namespace std; int answer=100000; int maxsize=1; int renshu; int anser(int m,int n,int l,int r,int a[])//表示m堆书，n个学生在分摊之后，返回学生所看书的最大页数 { // cout<<"m="<<m<<" n="<<n<<" l="<<l<<endl; if(n==1)//如果只有一个学生，就直接返回a数组中的值之和 { int sum=0; for(int i=l;i<=r;i++) { sum+=a[i]; } return sum; } else if(m==n)//若书堆数和学生数相同，因为要保证每个学生都有书看，而且数组a已经排好序了，所以直接返回最后一个数即可 { return a[r]; } else if(m<n)//此种情况会导致有学生没有书看，所以返回零（这个不大确定，我是乱写的） return 0; else if(m>n)//当书堆数大于学生人数时 { int k=0; for(int i=l;i<=m-n+l;i++)//表示列举可能的组合 ...这里不知道咋解释 { k+=a[i]; maxsize=max(k,anser(m-i+l-1,n-1,i+1,r,a)); if(n==renshu) { answer=min(answer,maxsize); } } } } int main() { int t,m,n; cin>>t;//t表示测试案例数 for(int j=0;j<t;j++) { cin>>m>>n;//m表示书堆的数目，n表示学生数目 renshu=n; int *a=new int[m+1]; for(int i=0;i<m;i++) cin>>a[i]; anser(m,n,0,m-1,a);//递归求解 cout<<answer; delete [] a; answer=100000; } return 0; }
2、保存的最大值是局部的
问题分析
可以对比思路1实现。原来b也通过answer返回了，到上一层求b又有一次max的筛选，得到的才是最大值。
直接将b保存下来，只经过了与本层k的比较，就相当只比较了两个人的看书量，不是该分配情况下所有人看书最多的那一个。
b数组应该存的是若干个最大值，然后通过排序最小化最大值。现在你代码并没有保证存的b是个“最大值”
问题代码版本
#include<iostream> #include<vector> #include<cstdlib> #include<algorithm> using namespace std; int renshu,book; vector<int>v; vector<int>::iterator it; int maxsize=100000; void anser(int m,int n,int l,int r,int a[],int &b)//表示m堆书，n个学生在分摊之后，返回学生所看书的最大页数 { if(n==1) { int sum=0; for(int i=l;i<=r;i++) { sum+=a[i]; } b=sum; return ; } else if(m==n) { b=a[r]; return ; } else if(m<n) { b = 8848; return; } else if(m>n) { int k=0; for(int i=l;i<=m-n+l;i++) { if(n==1) break; else if(m==n) break; k+=a[i]; int temp; anser(m-i+l-1,n-1,i+1,r,a,temp); b=max(k,temp); v.push_back(b); } return; } } int main() { int t,m,n,b=0,sum=0; cin>>t;//t表示测试案例数 for(int j=0;j<t;j++) { sum=0; cin>>m>>n;//m表示书堆的数目，n表示学生数目 book=m; renshu=n; int *a=new int[m+1]; for(int i=0;i<m;i++) { cin>>a[i]; sum+=a[i]; } if(n==1) cout<<sum<<endl; else if(m==n) cout<<a[m-1]<<endl; else { anser(m,n,0,m-1,a,b);//递归求解 sort(v.begin(),v.end()); cout<<*v.begin()<<endl; } delete [] a; } return 0; }
运行结果
算法分析
思路1
本来枚举的时间复杂度应为 O ( 2 n ) \Omicron (2^n)O(2
n
) （n 为书数量），每本书都有分给当前同学和分给下一个同学两种选择。不过还有剪枝的优化。
思路2
采用二分搜索的时间复杂度为 O ( l o g ( m ) ) \Omicron (log(m))O(log(m)) （m 为桶数），但每次判断桶容量是否合适都是在遍历物品序列，遍历的时间复杂度为 O ( n ) \Omicron(n)O(n) (n 为物品数量）。
因此总的时间复杂度应为：
