Uva 714 Copying Books

#uva 714 #binary search

題目來源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=655

題意：先給有N筆測資，以前的書是手抄的，現在有k本書和m位工人，希望你寫出一個程式，讓每位工人分到的頁數是相近的，且每位工人都要分到，若有多組解，以index較大的工人，頁數較多，並以 ' / ' 分隔，輸出答案於一行。

胡言亂語：

一開始以為要排序，就將book依頁數由小排到大，但最後發現根本不用XD。

這題使用的方法是Binary Search，演算法如下：

	while(upper_bound>lower_bound){
	//從上限和下限中間取中間值 u
	//u表示每個工人最多可分到的頁數
	u = (upper_bound+lower_bound)/2;
	//計算k本書是否可以剛剛好分成m份
	if(不行)
	then range：u~ upper_bound
	else
	then range：lower_bound ~u
	}

view raw .cpp hosted with ❤ by GitHub

當upper_bound<lower_bound的時候就可以跳出迴圈(loop)，一開始是想說找到了，就可以跳出來，但發現有時候找到的非最小值，所以要持續找到最小值才正確

而最後輸出的部分，因為題目要求若有多組解，後面工人的頁數盡量多一點，別想太複雜，從後面分配輸出就好了XD，思考一下，最後用的stack，因為可以從後面開始存，最後pop掉就好：

	for(int i=0 ;i<m ;i++){
	tag = u;//剛剛找到的臨界值
	//j>=(m-i-1)表示書要大於等於工人數
	//因為每個人都要拿到書
	while(tag>0&&j>=(m-i-1)){
	tag-=book[j];
	if(tag>=0) {str.push(book[j]);j--;}
	}
	str.push(-1);//打入tag，等等output的時候
	//如果讀到'-1'則輸出 ' / '
	}

view raw .cpp hosted with ❤ by GitHub

[補]stack的用法：

	#include<stack>
	//宣告stack ：str
	stack <int> str;
	//stack是先入後出
	//有點像是在疊書，最後放的書可以最先拿起來
	str.pop();//把stack的書拿起來
	str.push();//將書疊到stack中
	int x = str.top();//x = stack最上面那本書

view raw .cpp hosted with ❤ by GitHub

程式碼：

	#include<cstdio>
	#include<stack>
	#include<iostream>
	#include<algorithm>
	using namespace std;
	stack <long long int> str;
	int main(){
	long long int m,N,k,upper,lower,u;
	long long int book[502];
	scanf("%lld",&N);
	while(N--){
	scanf("%lld %lld",&k,&m);
	upper = 0;
	lower = 0;
	for(int i=0;i<k;i++){
	scanf("%lld",&book[i]);
	upper += book[i];
	}
	long long int tag,j;
	while(upper>lower){
	u = (upper+lower)/2;
	j = 0;
	for(int i=0 ;i<m ;i++){
	tag = u;
	while(tag>0){
	tag-=book[j];
	if(tag>0) j++;
	}
	}
	if(j<k) lower = u+1;
	else upper = u;
	}
	j = k-1;
	for(int i=0 ;i<m ;i++){
	tag = u;
	while(tag>0&&j>=(m-i-1)){
	tag-=book[j];
	if(tag>=0) {str.push(book[j]);j--;}
	}
	str.push(-1);
	}
	str.pop();
	while(str.size()){
	if(str.top()>=0) printf("%lld",str.top());
	else printf("/");
	str.pop();
	if(str.size()) printf(" ");
	}
	printf("\n");
	}
	}

view raw uva 714.cpp hosted with ❤ by GitHub