j038 - 11824 - A Minimum Land Price
題目描述
題目要求在預算限制下，以最低價格購買多塊土地。每塊土地的價格會隨著購買年份的增加而指數增長。目標是找到在預算內購買所有土地的最小總成本。
解題思路
本題的解題思路是使用貪心演算法。首先，將土地成本由小到大排序。然後，按照排序後的順序依次購買土地。對於第 i 塊土地，其價格為 2 * (土地成本)^i。在每次購買土地後，檢查總成本是否超過預算。如果超過預算，則輸出 "Too expensive"。否則，繼續購買下一塊土地。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是土地數量。排序操作佔據主導地位。
- 空間複雜度: O(n)，用於儲存土地成本的陣列。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
long long t,x,a[41],ma=5000000;
int main(){
cin >> t;
while(t--){
long long n=0,s=0;
while(cin >> x){
if(x==0)break;
a[n++]=x;
}
sort(a,a+n);
for(int i=n-1,j=0;i>=0;--i,++j){
long long ba=a[i];
for(int k=0;k<j;++k){
if(ba>ma)break;
ba*=a[i];
}
s+=ba*2;
if(s>ma)break;
}
if(s>ma){
cout << "Too expensive\n";
}
else{
cout << s << "\n";
}
}
}