20分求助

P1478 陶陶摘苹果(升级版)

miaozheyuan @ 2023-08-10 14:25:05

#include <iostream>
using namespace std;

struct apple {
    int a, b;
    void read() {
        cin >> a >> b;
    }
}ap[5005];

bool cmp(apple x, apple y) {
    return x.a < y.a;
}

int main() {
    int s, a, b;
    int n;
    cin >> n >> s >> a >> b;
    a += b;
    for (int i = 1; i <= n; ++i) {
        ap[i].read();
    }
    sort(ap + 1, ap + n + 1, cmp);
    int cnt = 0, i = 1, sum = 0;
    while(true) {
        if (ap[i].a > a) {
            ++i;
            continue;
        }
        if(cnt + ap[i].b >= s) {
            break;
        }
        sum++;
        cnt += ap[i].b;
        ++i;
    }
    cout << sum;
    return 0;
}

by xxxxxzy @ 2023-08-10 14:31:45

?这个题不是背包吗


by miaozheyuan @ 2023-08-10 14:49:59

应该是贪心吧


|