社区讨论
向各位求助
B4071[GESP202412 五级] 武器强化参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mhjasdwo
- 此快照首次捕获于
- 2025/11/03 23:31 4 个月前
- 此快照最后确认于
- 2025/11/03 23:31 4 个月前
https://www.luogu.com.cn/record/234383100
CPP#include "algorithm"
#include "iostream"
using namespace std;
struct Q
{ //强化材料
int sp; //适配
int cost; //花费
};
int n, m; //小杨有 n 种武器和 m 种强化材料
Q q[1001]; //强化材料数组
bool cmp(Q x, Q y)
{
return x.cost < y.cost;
//按修改所花费的价钱排序 是一个贪心策略
}
int p[1001] = {0}; //每一种武器拥有的适配它的材料数
int FMS(int length)
{
//找出最大下标 若下标对应为1 返回-1
int max_index = 1;
for (int i = 2;i<=length;i++)
{
if (p[i] > p[max_index])
{
max_index = i;
}
}
if (max_index == 1)
{
return -1;
}
else return max_index;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> q[i].sp >> q[i].cost;
p[q[i].sp]++;
}
sort(q, q + m + 1, cmp); //对强化材料数组进行从小到大的排序
int maxl = -1000; //找出拥有强化材料数量最多的武器的武器数量
int curr = p[1];
long long ans = 0;
int subscript = 1;
for (int i = 2;i <= n;i++)
{
if (p[i] > maxl)
{
maxl = p[i];
}
}
while (curr <= maxl) //直到 严 格 大 于 其他所有的为止
{
if (q[subscript].sp != 1)
{
p[q[subscript].sp]--; //先减
q[subscript].sp = 1; //后改
curr++;
int max_s = FMS(n); // p数组的最大值要动态变化 这句话要找出当前p数组的最大值
if (max_s == -1) //p[1]已经是最大值
{
break;
}
maxl = p[max_s];
ans += q[subscript].cost;
subscript++; //继续下一个
}
else
{
subscript++; //直接跳过这一个
}
}
cout << ans;
return 0;
}
感谢你们
回复
共 5 条回复,欢迎继续交流。
正在加载回复...