[GESP202412 五级] 奇妙数字
题目描述
小杨认为一个数字 x 是奇妙数字当且仅当 x=pa，其中 p 为任意质数且 a 为正整数。例如，8=23，所以 8 是奇妙的，而 6 不是。
对于一个正整数 n，小杨想要构建一个包含 m 个奇妙数字的集合 {x1,x2,⋯,xm}，使其满足以下条件：
- 集合中不包含相同的数字。
- x1×x2×⋯×xm 是 n 的因子（即 x1,x2,⋯,xm 这 m 个数字的乘积是 n 的因子）。
小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。
输入格式
第一行包含一个正整数 n，含义如题面所示。
输出格式
输出一个正整数，代表满足条件的集合最多包含的奇妙数字个数。
输入输出样例
输入 #1复制
128
输出 #1复制
3
说明/提示
样例解释
关于本样例，符合题意的一个包含 3 个奇妙数字的集合是 {2,4,8}。首先，因为 2=21，4=22，8=23，所以 2,4,8 均为奇妙数字。同时，2×4×8=64 是 128 的的因子。
由于无法找到符合题意且同时包含 4 个奇妙数字的集合，因此本样例的答案为 3。
数据范围
对于 100% 的数据，保证 2≤n≤1012。
| 子任务编号 | 得分占比 | n |
|---|---|---|
| 1 | 20% | ≤10 |
| 2 | 20% | ≤1000 |
| 3 | 60% | ≤1012 |
题意简述
重新分配强化材料给武器，使第 1 种武器材料数最多，且总转移成本最小。
思路
读取武器的种类数 n 和强化材料的数量 m。对于每个强化材料，记录其对应的武器编号和成本，并统计每种武器的材料数量和成本列表。
对每种武器的强化材料成本列表进行排序，以便后续能够高效地选择成本最低的材料。
我们定义一个函数 f：该函数计算了在给定第 1 种武器需要达到的强化材料数量 x 时，将其他武器的材料转移到第 1 种武器所需的最小成本。
函数内部通过遍历每种非第 1 种武器，计算需要转移的材料数量，并从该武器的成本列表中选择成本最低的材料进行转移。如果转移后第 1 种武器的材料数量仍然不足 x，则从剩余的材料中选择成本最低的进行补充。
我们遍历一个范围，从第 1 种武器的初始材料数量到总材料数量。对于每个可能的 x 值，调用函数 f 计算转移成本，并更新全局最小成本。最终输出全局最小成本作为结果。
code!!!
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> cost[1010];
int n,m,ans=LONG_LONG_MAX;
void work(int x){int money=0;int d=x-cost[1].size();vector<int>v;for(int i=2;i<=n;i++){int isz=cost[i].size();int need=max(isz-(x-1),0ll);for(int j=0;j<need;j++){money+=cost[i][j];}d-=need;for(int j=need;j<cost[i].size();j++)v.push_back(cost[i][j]); }if(d>0){sort(v.begin(),v.end());for(int i=0;i<v.size()&&d>0;i++){money+=v[i];d--;}}ans=min(ans,money);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){int p,c;cin>>p>>c;cost[p].push_back(c);}for(int i=2;i<=n;i++)sort(cost[i].begin(),cost[i].end());int s1=cost[1].size();if(s1==0)s1=1;for(int x=s1;x<=m;x++){work(x);}cout<<ans;return 0;//华丽结束
}//完结散花
/*by huntercwo 2025 0601 20:01:22