題敘
http://domen111.github.io/UVa-Easy-Viewer/?907
在一趟路途中總共過了 $k$ 天晚上，也就是 $k+1$ 天
在 $n$ 個暫停點之間加上起點與終點共包含 $n+1$ 條路連接兩兩暫停點，每個路徑都有一個距離
求在經過 $k$ 天晚上的情況下，一天行走距離的最小值為多少
想法
如果說一日行走距離 $m$ 可以在 $k+1$ 天走完，那麼距離 $m+1$ 也一定可以
所以觀察到行走距離具有單調性
枚舉一天行走的距離，如果所需的時間超過 $k$ ，就將枚舉的上界調整，否則調整下界
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int n,k,Min=0,Max=0,arr[605];
int search(int l,int r,int p){
while(l<r){
int mid=(l+r)>>1;
int dis=arr[0],day=0;
for(int i=1 ; i<=n ; i++){
if(dis+arr[i]>mid){
day++;
dis=arr[i];
}
else dis+=arr[i];
}
if(dis<=mid) day++;
if(day>p) l=mid+1;
else r=mid;
}
return l;
}
int main(){
while(cin>>n>>k){
Min=Max=0;
for(int i=0 ; i<=n ; i++){
cin>>arr[i];
Min=max(Min,arr[i]);
Max+=arr[i];
}
cout<<search(Min,Max,k+1)<<"\n";
}
return 0;
}
|
複雜度分析
二分搜尋的上界與下界的差值約若為 $\sum arr[i]$
複雜度約為 $O(log_2 \sum arr[i])$