# 【UVA】907.Winterim Backpacking Trip

## [907.Winterim Backpacking Trip](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=848>)

## 時間複雜度

* $O(<N*log(D)>)$

## 解題想法

這題很難，我覺得是很難理解
題目給你總共有N個露營區，以及K個晚上，接下來的側資是每個露營區的距離。
舉個例子:
假設，N=4、K=3、{7,2,6,4,8}代表每個露營區的距離，大概的路徑就是O(原點)-->7-->2-->6-->4-->8-->END，露營區的位置是固定的，所以你必須走到露營區才能休息，總不可能停在半路上，所以我們需要找出一個平衡點->在K個晚上可以走完，也不會超過自身負擔的走路距離。
※目標:時間內走完，不會太有負擔，

Approach:
這題可以透過二分搜(Binary Search)直接解，但還要注意**能不能走完跟會不會超過限制天數**，上下界很好理解，下界就是這幾段的最大距離，如果不是最大距離，你再怎麼走都走不完，因為走不夠遠，到不了下個露營區，而上界就是全部的距離，以極端情況來說，你一天就走完全程。

接下來是判斷部分，你可以想成模擬登山，這個距離我開始走，能不能走完，會不會造成很大負擔，進而用bool true/false表達，如果可以的話，確認能不能同一天再走更少一點，這樣就能更輕鬆地達成;如果不行，那我是不是可以每天走更多一點，這樣也許在時間內能走完。

## 完整程式

<你的程式>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
bool check(ll mid,ll nights,vector<ll> dis){
	ll count=0,nights_spend=0,i=0;
	for(int x=0;x<dis.size();x++){
		if(dis[x]>mid)return false;
		if(count+dis[x]>mid){
			nights_spend++;
			count=dis[x];
		}
		else{
			count+=dis[x];
		}
	
	}
	if(nights_spend>nights)return false;
	else					 return true;
}
	
int mid_dis(vector<ll> dis,ll nights){
	ll  largest=0,least=*max_element(dis.begin(),dis.end());
	for(auto&c:dis)largest+=c;
	ll  nights_spend=0,current_distance=0,ans;
	while(least<=largest){
		ll mid = least + (largest-least)/2;
		
		if(check(mid,nights,dis)){
			largest = mid-1;
			ans=mid;
		}
		else{
			least = mid+1;
		}
	
	
	}
	return ans;
}
int main(){
  ll campsites,nights,input;
  while(cin>>campsites>>nights){
  	vector<ll> dis;
  	
  	for(ll i=0;i<=campsites;i++){cin>>input;dis.push_back(input);}
  		cout<<mid_dis(dis,nights)<<endl;
  }
  return 0;
}