P1478 陶陶摘苹果（升级版）

eofitg · 2025-05-20 14:31:13 · 个人记录

P1478 陶陶摘苹果（升级版）

思路

胳膊真正长度其实就是 a + b

苹果根据所需力气从小到大排序，高度够底及需花力气足够就采摘，力气花光直接 break

记录

一次就AC

AC代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp_sort(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int s;
    int a, b;
    vector<pair<int, int>> apples;
    int ans = 0;

    cin >> n >> s;
    cin >> a >> b;
    int len = a + b;

    for (int i = 0; i < n; i ++) {
        int xi, yi;
        cin >> xi >> yi;
        apples.emplace_back(xi, yi);
    }

    sort(apples.begin(), apples.end(), cmp_sort);

    for (auto apple : apples) {
        if (s - apple.second < 0) break;
        if (apple.first <= len) {
            ans ++;
            s -= apple.second;
        }
    }

    cout << ans;

    return 0;
}

总结

很简单的排序问题，属于最直接了当显而易见的那种贪心策略

—— 2025/05/20