AC

原题链接：8970.Lorry
userId_undefined

钢叉78maxpro半仙

出道萌新倔强青铜

2025-08-02 19:04:19

发布于：广东

5阅读
0回复
0点赞

#include <iostream>
#include <vector>
#include <algorithm>//#include<bits/stdc++.h> 同理
using namespace std;

typedef long long ll;//typedef > ll <long long>

struct Item {//使用struct
int val;
int id;
Item(int v, int i) : val(v), id(i) {}
};

bool cmp(const Item& a, const Item& b) {
return a.val > b.val;//bool
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);//效率高

int n, v;
cin >> n >> v;

vector<Item> a, b;
for (int i = 1; i <= n; i++) {
    int t, p;
    cin >> t >> p;
    if (t == 1) {
        a.push_back(Item(p, i));
    } else {
        b.push_back(Item(p, i));
    }
}

sort(a.begin(), a.end(), cmp);//排序
sort(b.begin(), b.end(), cmp);

int na = a.size();
int nb = b.size();

vector<ll> preA(na + 1, 0);
for (int i = 0; i < na; i++) {
    preA[i + 1] = preA[i] + a[i].val;//for
}

vector<ll> preB(nb + 1, 0);
for (int i = 0; i < nb; i++) {
    preB[i + 1] = preB[i] + b[i].val;//for
}

ll best = 0;
int best_j = 0, best_k = 0;
int max_j = min(nb, v / 2);

for (int j = 0; j <= max_j; j++) {//for
    ll rest = v - 2LL * j;
    if (rest < 0) break;
    int k = min(na, (int)rest);
    ll total = preB[j] + preA[k];
    if (total >= best) {//判断
        best = total;
        best_j = j;
        best_k = k;
    }
}

cout << best << endl;//特殊

vector<int> ans;
for (int i = 0; i < best_j; i++) {
    ans.push_back(b[i].id);//特4
}
for (int i = 0; i < best_k; i++) {
    ans.push_back(a[i].id);//特5
}

sort(ans.begin(), ans.end());

if (ans.empty()) {
    cout << endl;
} else {
    for (int i = 0; i < ans.size(); i++) {
        if (i > 0) cout << " ";
        cout << ans[i];//cout 即可
    }
    cout << endl;
}

return 0;

}

userId_undefined
去预览
0/2000

全部评论 2

热门讨论