Koios1143的筆記

TOJ 556

發表於 更新於 分類於

TOJ 556

題目

https://toj.tfcis.org/oj/pro/556/

有 $N$ 項工作，為了好好管理進度，我們把每一份工作都分成了 $K$ 份

對於第 $i$ 項工作每天可以完成 $a_i$ 份，並且每天都會做每一項工作

因為怕工作會做不完，我們有 $M$ 筆經費可以將工作外包

每一經費對於第 $i$ 項工作可以將其中的 $b_i$ 份工作外包，並且不需考慮外包的作業時間

請問在最佳分配經費的情況下，最少可以在幾天之內完成 $N$ 份工作

$$
1 \leq N \leq 10^5\
1 \leq K \leq 10^9\
0 \leq M \leq 10^9\
1 \leq a_i \leq 10^9\
1 \leq b_i \leq 10^9
$$

想法

如果說 $X$ 天可以把工作處理完成，那麼 $X+1$ 天也一定可以

發現到天數是具有單調性的，那麼要求最小的天數就可以用二分搜來完成

二分搜最小所需要的天數 $X$，確認 $X$ 是否可行來調整左界與右界

那麼要怎麼確認 $X$ 天能不能完成呢?

我們可以把每一項工作都先減去 $X$ 天自己做可以完成的工作量

那麼剩下的所有工作就必須要外包才能完成了

最後計算需要外包的數量，就可以判斷是否可以在 $X$ 天完成了!

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
36
37
38
//By Koios1143
#include<iostream>
using namespace std;
long long n, k, m, L=0, R=1e9+10, A[100005], B[100005], tmp[100005];

long long search(long long l, long long r, long long p){
	while(l<r){
		long long mid = (l+r)/2, cnt=0;
		for(long long i=0 ; i<n ; i++){
			// 先扣除 mid 天可以自己完成的工作量
			tmp[i] = k - A[i]*mid;
			if(tmp[i] > 0){
				// 剩下的全部外包
				cnt += tmp[i]/B[i];
				if(tmp[i] % B[i] > 0) cnt++;
			}
		}
		if(cnt > p) l = mid + 1;
		else r = mid;
	}
	return l;
}

int main(){
	cin>>n>>k>>m;
	for(long long i=0 ; i<n ; i++){
		cin>>A[i];
		R = min(R, A[i]);
	}
	for(long long i=0 ; i<n ; i++){
		cin>>B[i];
	}
	// 最大工作天數為 (工作份數K / 一天處理最小的工作量)
	R = k/R + 1;
	cout<<search(L, R, m)<<"\n";

	return 0;
}

時間複雜度分析

輸入時間複雜度為 $O(n)$

二分搜的右界為 $R’ = k / min(R) + 1$

搜尋時間複雜度為 $O(nlog{R’})$

總時間複雜度為 $O(n + nlog{R’})$