c634 - 基礎排序 #2-1 ( 質因數和 ez)
題目描述
題目要求解析給定的字串，提取其中的字母部分 (T) 和數字部分 (N)，計算 N 的質因數和，然後根據質因數和、T 字串和 N 的值對字串進行排序。排序規則優先考慮質因數和遞減，其次是 T 字串遞增，最後是 N 值遞減。
解題思路
程式碼首先預先計算出 10001 以內的質數，並將其儲存在 pr2 陣列中。然後，對於輸入的每個字串，程式碼會提取字母部分和數字部分。接著，計算數字部分的質因數和。最後，使用自定義比較函數 cmp 對字串進行排序，排序函數按照題目要求的規則進行比較。
複雜度分析
- 時間複雜度: O(n * m + n log n)，其中 n 是輸入字串的數量，m 是每個字串的長度。預先計算質數的時間複雜度是 O(10001 log log 10001)，可以視為常數時間。提取字母和數字部分的時間複雜度是 O(m)。計算質因數和的時間複雜度是 O(sqrt(N))，其中 N 是數字部分的值，最壞情況下是 O(sqrt(10000))，可以視為常數時間。排序的時間複雜度是 O(n log n)。
- 空間複雜度: O(n + 10001)，其中 n 是輸入字串的數量，10001 是質數陣列的大小。
程式碼
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct n{
string name,t;
int num,ns;
};
int it,pr[10001]={1,1},pr2[1231],it2;
n a[100001];
inline int p(int k){
int rt=0;
for(int i=0;pr2[i]<=k;++i){
if(k%pr2[i]==0){
k/=pr2[i];
rt+=pr2[i];
}
}
return rt;
}
inline bool cmp(n x,n y){
if(x.ns>y.ns||(x.ns==y.ns&&x.t<y.t)||(x.ns==y.ns&&x.t==y.t&&x.num>y.num))return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=2;i<101;++i){
for(int j=i+i;j<10001;j+=i){
pr[j]=1;
}
}
for(int i=2;i<=10001;++i){
if(pr[i]==0){
pr2[it2]=i;
++it2;
}
}
while(cin >> a[it].name){
int nl=a[it].name.length();
string tmp;
int tmp2=0;
for(int i=0;i<nl;++i){
if(a[it].name[i]>='0'&&a[it].name[i]<='9'){
tmp2*=10;
tmp2+=a[it].name[i]-'0';
}
else{
tmp+=a[it].name[i];
}
}
a[it].t=tmp;
a[it].num=tmp2;
a[it].ns=p(tmp2);
++it;
}
sort(a,a+it,cmp);
for(int i=0;i<it;++i){
cout << a[i].name << "\n";
}
}