P1478 陶陶摘苹果（升级版）题解

#include<iostream> #include<vector> #include<algorithm> // 定义结构体xy，表示苹果的属性 // x: 苹果的高度 // y: 摘取苹果需要的力量/花费 struct xy { int x, y; }; // 比较函数，用于排序 // 按照苹果的花费y从小到大排序 // 这样排序后，花费小的苹果会排在前面 int cmpxy(const xy &a, const xy &b) { return a.y < b.y; } using namespace std; int main() { // 输入数据 int n, s, a, b; // n:苹果总数, s:拥有的总力量, a:身高, b:凳子高度 cin >> n >> s >> a >> b; // 计算能够到的最大高度：身高 + 凳子高度 a += b; // 创建向量v，用于存储能够到的苹果 vector<xy> v; // 输入所有苹果的信息，并筛选能够到的苹果 for(int i = 0; i < n; i++) { xy p; // 临时变量存储一个苹果的信息 cin >> p.x >> p.y; // 输入苹果的高度和花费 // 如果苹果的高度不超过能够到的最大高度，则将其加入向量v if (p.x <= a) { v.push_back(p); } } // 对能够到的苹果按照花费从小到大排序（贪心策略） // 这样我们可以优先摘取花费小的苹果，从而摘到更多的苹果 sort(v.begin(), v.end(), cmpxy); int sum = 0; // 记录摘到的苹果数量 // 遍历排序后的苹果向量 for (int x = 0; x < v.size(); x++) { // 如果当前苹果的花费不超过剩余的力量 if (v[x].y <= s) { s -= v[x].y; // 花费力量摘取这个苹果 sum++; // 摘到的苹果数量加1 } // 注意：这里没有break，因为即使当前苹果无法摘取，后续可能有更便宜的苹果 // 但由于我们已经排序了，所以实际上后续苹果的花费不会更小 // 不过题目保证力量s非负，且输入合理，所以这里逻辑正确 } // 输出最多能摘到的苹果数量 cout << sum << endl; return 0; }