f029 - Error

🔗 前往 ZeroJudge 原題

題目描述

題目要求找到一個最小的 x 值，使得可以將 n 個數字 a[i] 分配給 x 個伺服器，每個伺服器負擔的請求數不超過 x。更具體地說，對於每個 a[i]，需要 ceil(a[i] / x) 個伺服器來處理這些請求。總共需要的伺服器數量不能超過 x。

解題思路

這題的核心思想是使用二分搜尋來尋找最小的 x 值。由於題目要求最小的 x，我們可以設定一個搜尋範圍，從 n (最少需要的伺服器數量) 到 sum (所有請求的總和，即最壞情況下每個伺服器處理一個請求)。

在二分搜尋的過程中，對於每個 x 值，我們需要判斷是否可以使用 x 個伺服器來處理所有請求。judge(x) 函數用於判斷這個條件。judge(x) 函數按照 a[i] 降序排列，然後依次計算每個 a[i] 需要的伺服器數量，並將其加到總伺服器數量 ct 中。如果 ct 超过 x，或者 tx (伺服器編號) 小於等於 0，則說明 x 不足夠，返回 false。

二分搜尋的目標是找到最小的 x，使得 judge(x) 返回 true。因此，在 judge(x) 返回 true 時，我們繼續在左半部分搜尋，以找到更小的 x 值。

複雜度分析

• 時間複雜度: O(t * n * log(sum))，其中 t 是測試案例數量，n 是陣列大小，sum 是陣列元素的總和。sort(a, a+n) 的時間複雜度是 O(n log n)，bs 函數調用 judge 函數，judge 函數的時間複雜度是 O(n)，而 bs 函數的時間複雜度是 O(log(sum))。
• 空間複雜度: O(n)，主要用於儲存陣列 a。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int t,n,a[1005];
bool judge(int x){
	int ct=0,tx=x;
	for(int i=n-1;i>=0;--i){
		ct+=a[i]/tx+(a[i]%tx==0?0:1);
		--tx;
		if(ct>x)return 0;
		if(tx<=0)return 0;
	}
	return 1;
}
int bs(int l,int r){
	if(l>r)return l;
	int m=(l+r)/2;
	if(judge(m)){
		return bs(l,m-1);
	}
	return bs(m+1,r);
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> t;
	for(int i=0;i<t;++i){
		cin >> n;
		int sum=0;
		for(int j=0;j<n;++j){
			cin >> a[j];
			sum+=a[j];
		}
		sort(a,a+n);
		cout << bs(n,sum) << "\n";
	}
}