想用贪心做,结果WA了
查看原帖
想用贪心做,结果WA了
1372590
uuplayer楼主2024/10/2 22:47

各位大佬帮忙看看我这个代码,我想尝试用贪心解决,样例稳稳过了,其他测试点全部稳稳的WA了

#include<bits/stdc++.h>
using namespace std;
int t, m;
struct st {
    int ti, v;// ti表示采这个药的时间,v表示这个药的价值
} a[10001];
bool cmp(const st &x, const st &y) {
    return (long long)x.v * y.ti > (long long)y.v * x.ti;//优先考虑时间和价值比例最大的药,这里把除号方式改为了交叉相乘,同理亦是正确的。
}
int main() {
    cin >> t >> m;
    vector<st> f;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i].ti >> a[i].v;
        if (a[i].ti <= t) { // 只保留可以采集的草药
            f.push_back(a[i]);
        }
    }
    sort(f.begin(), f.end(), cmp);
    int ans = 0, tmp = 0;
    int index = 0; // 追踪草药的索引
    while (index < f.size() && tmp < t) {
        if (tmp + f[index].ti <= t) { //确保不会超过总时间
            tmp += f[index].ti;
            ans += f[index].v;
        } else { // 如果加上这个草药超过了总时间,则直接退出循环
            break;
        }
        index++; // 移动到下一个草药
    }
    cout << ans << endl;
    return 0;
}

2024/10/2 22:47
加载中...