題目連結: https://zerojudge.tw/ShowProblem?problemid=f815
# 解題思路
我們可以透過先假設一個結果，再判斷該結果是否為最佳，
假設錢的總數足夠達到該結果，就將結果往上調一等，
若不足夠，則往下調整一等，直到最終結果是符合結果中的最大值。
但是，依序的搜索對於這題而言太過緩慢，又因為調整的結果情況為一次一次的，類似於查找已排序序列的結果
因此，我們這題可以透過對答案二分搜的方式，將答案逼近到我們想要的目標結果。
(這題的程式碼以左閉右開的形式撰寫)
# 程式碼
#include <iostream> | |
using namespace std; | |
#define int long long | |
int lv[20005],n; | |
int gold(int m) // 計算到等級 m 需要的金幣 | |
{ | |
int sum=0; | |
for(int i=0;i<n;i++) | |
if (lv[i]<m) // 如果士兵等級 < m | |
sum += (lv[i]-m)*(lv[i]-m); // 計算需要的花費後加總 | |
return sum; | |
} | |
signed main(){ | |
int c,L=1,R=20000005,m; // 左閉，右開 | |
cin >> n >> c; | |
for(int i=0;i<n;i++) | |
cin >> lv[i]; | |
while(L<R) | |
{ | |
m = (L+R)/2; // 預期的等級 m | |
if (gold(m)>c) // 需要的金幣 > 預算 | |
R = m; // 調整 R | |
else | |
L = m+1; // 調整 L | |
} | |
cout << R-1 << endl; | |
return 0; | |
} |
