[TIOJ] 1465. H遊戲密笈 - EXTREME

題目連結:http://tioj.infor.org/problems/1465

---

本題其實跟TIOJ 1432很像，一樣都二分搜答案，上界是序列和，下界是序列中最大值-1，不過他比較麻煩的地方是他在輸出時要把劃分好的結構輸出，所以當我們搜到答案以後，還要再從後面爬一遍，然後看要把分隔符號塞在那，不過為何是從後面爬呢，因為他想要讓前面的人的項數最少，那就是要讓後面的人項數最多，所以就讓後面每個人都拿到極限就好，另外一個值得注意的重點是因為他要讓每個人都抄到書，所以我們還要判斷一下剩下的項數根剩下的人數是否一樣了，若是就要在每個地方加上分隔符號

#include <stdio.h>
#include <vector>
typedef long long lld;

#define PB push_back

using std::vector;

int n,m;
int arr[500 + 10];
inline bool test(int);

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d %d",&n,&m);
		lld l=0,r=0;
		for(int i=0;i<n;i++){
			scanf("%d",&arr[i]);
			r+=(lld)arr[i];
			l=(l>arr[i])?l:arr[i];
		}
		l-=1;
		while(r-l != 1){
			if(test((r+l)/2))
				r=(r+l)/2;
			else
				l=(r+l)/2;
		}
		vector<int> point;
		lld plus=0;
		int p = m-2;
		for(int i=n-1;i>=0;i--){
			if(plus + arr[i] > r){
				plus = arr[i];
				point.PB(-1);
				p--;
			}else{
				if(i == p){
					point.PB(-1);
					p--;
				}
				plus+=arr[i];
			}
			point.PB(arr[i]);
		}
		for(int i=point.size()-1;i>=0;i--){
			point[i]==-1?putchar('/'):printf("%d",point[i]);
			putchar(' ');
		}
		putchar('\n');
	}
}

inline bool test(int maxS){
	int k=1;
	lld plus=0;
	for(int i=n-1;i>=0;i--){
		if(plus + arr[i] > maxS){
			plus=arr[i];
			k++;
			if(k>m) return false;
		}else{
			plus+=arr[i];
		}
	}
	return true;
}