社区讨论

向各位求助

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 条回复,欢迎继续交流。

正在加载回复...