c630 - 基礎排序 #3 ( a ^ n 排大小 )
題目描述
題目要求讀取多組 a 和 n 的值，計算 a 的 n 次方，並按照 a^n 的值從大到小排序輸出。如果 a^n 的值相同，則按照 a 的值從大到小排序。
解題思路
由於 a 和 n 的範圍較大，直接計算 a^n 可能會超出數值範圍。因此，我們使用對數來避免溢位。根據對數的性質，log(a^n) = n * log(a)。我們計算每個 (a, n) 對應的 n * log(a) 的值，然後按照這個值對 (a, n) 對進行排序。排序後，按照題目要求輸出 a 和 n 的值。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是輸入的 (a, n) 對的數量。主要時間花在排序上。
- 空間複雜度: O(N)，用於儲存輸入的 (a, n) 對。
程式碼
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct lg{
float v,a,b;
};
inline bool cmp(lg x,lg y){
if(x.v>y.v||(x.v==y.v&&x.a>y.a))return 1;
return 0;
}
lg ans[10000];
int it=0;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> ans[it].a >> ans[it].b){
ans[it].v=log(ans[it].a)*ans[it].b;
++it;
}
sort(ans,ans+it,cmp);
for(int i=0;i<it;++i)
cout << ans[i].a << " " << ans[i].b << "\n";
}