c633 - 基礎排序 #2-2 ( 質因數和 )
題目描述
題目要求解析包含字母和數字的字串，提取其中的數字部分 (N) 和字母部分 (T)，計算 N 的質因數和，然後根據質因數和、T 字串和 N 的值對輸入字串進行排序並輸出。排序規則優先考慮質因數和遞減，其次考慮 T 字串遞增，最後考慮 N 值遞減。
解題思路
- 預處理質因數和: 首先，使用埃拉托斯特尼篩法預先計算出 1 到 1000000 每個數字的質因數和，並儲存在
ans陣列中。 - 解析輸入字串: 讀取輸入字串，將其分割為數字部分 (N) 和字母部分 (T)。
- 計算質因數和: 使用預先計算好的
ans陣列獲取 N 的質因數和。 - 建立結構體: 將字串、數字、字母部分和質因數和儲存在一個結構體
ss中。 - 排序: 使用
sort函數和自定義比較函數cmp對結構體ss的向量進行排序。比較函數按照質因數和遞減、T 字串遞增、N 值遞減的順序進行比較。 - 輸出: 輸出排序後的字串。
複雜度分析
- 時間複雜度: O(N log log N + M log M)，其中 N 是質因數和預處理的上限 (1000000)，M 是輸入字串的數量。埃拉托斯特尼篩法的時間複雜度為 O(N log log N)，解析字串和計算質因數和的時間複雜度為 O(M)，排序的時間複雜度為 O(M log M)。
- 空間複雜度: O(N + M)，其中 N 是質因數和預處理的上限 (1000000)，M 是輸入字串的數量。
ans陣列佔用 O(N) 空間，a向量佔用 O(M) 空間。
程式碼
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool p[1000001]={1,1};
int ans[1000001];
struct ss{
string s1,t;
int v,sum;
};
vector <ss> a;
string input;
bool cmp(ss x,ss y){
if(x.sum>y.sum||(x.sum==y.sum&&x.t<y.t)||(x.sum==y.sum&&x.t==y.t&&x.v>y.v))return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=2;i<=1000;++i)
for(int j=i+i;j<=1000000;j+=i)
p[j]=1;
for(int i=2;i<=1000000;++i)
if(p[i]==0)
for(int j=i;j<=1000000;j+=i)
ans[j]+=i;
while(cin >> input){
ss tmp;
tmp.s1=input;
string s2;
int su=0;
for(int i=0;i<input.length();++i){
if(input[i]>='0'&&input[i]<='9'){
su*=10;
su+=input[i]-'0';
}
else{
s2+=input[i];
}
}
tmp.v=su;
tmp.t=s2;
tmp.sum=ans[su];
a.push_back(tmp);
}
sort(a.begin(),a.end(),cmp);
for(int i=0;i<a.size();++i)
cout << a[i].s1 << "\n";
}