f815 - TOI_y21m4_a01遊戲升等

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在給定的金幣數量下，所有士兵至少可以升到哪個等級。每個士兵升級的成本是等級差的平方。目標是找到一個等級 U，使得將所有士兵升到至少 U 等級所需的總金幣數不超過給定的金幣數量，並且 U 是最小的滿足條件的等級。

解題思路

本題可以使用二分搜來解決。首先，將士兵的等級排序。然後，二分搜可能的等級 U。對於每個 U，計算將所有士兵升到至少 U 等級所需的金幣數。如果所需的金幣數不超過給定的金幣數量，則說明 U 是可行的，我們嘗試更大的 U。否則，說明 U 不可行，我們嘗試更小的 U。

judge(t) 函數用於判斷是否所有士兵都能升到等級 t。它計算升級所需的總金幣數，如果總金幣數小於或等於 m，則返回 true，否則返回 false。

bs(l, r) 函數執行二分搜，找到最小的等級 U，使得所有士兵都能升到至少 U 等級。

複雜度分析

• 時間複雜度: O(n log n + log(max_level))，其中 n 是士兵數量，max_level 是等級的最大值（在本例中為 20000000）。排序需要 O(n log n) 的時間，二分搜需要 O(log(max_level)) 的時間，每次二分搜的判斷需要 O(n) 的時間。
• 空間複雜度: O(n)，主要用於儲存士兵的等級。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
long long int n,a[20001],m,mi=20000000;
bool judge(long long int t){
	long long int tmp=m;
	for(int i=0;i<n;++i)
		if(a[i]<t){
			tmp-=(t-a[i])*(t-a[i]);
			if(tmp<0)return 0;
		}
	return 1;
}
long long int bs(long long int l,long long int r){
	if(l>r)return r;
	long long int mon=(l+r)/2;
	if(judge(mon))
		return bs(m+1,r);
	else
		return bs(l,m-1);
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0;i<n;++i)
		cin >> a[i];
	sort(a,a+n);
	cout << bs(a[0],20000000) ;
}