小美在玩游戏，游戏中有 n 个怪物，怪物的血量为 h，攻击力为 ai。小美的血量为 H，攻击力为 A，小美可以击败血量和攻击力都小于自己的怪物，并且打败后血量降为怪物的血量，攻击力降为怪物的攻击力。小美想知道最多可以打败多少怪物。
#include<bits/stdc++.h> #include<vector> using namespace std; typedef pair<int,int> P; bool cmp(P a, P b) { return a.first<b.first||(a.first==b.first&&a.second>b.second); } int main() { int n, H, A; cin >> n >> H >> A; vector<P>p(n); for(int i = 0; i < n; i ++) cin >> p[i].first; for(int i = 0; i < n; i ++) cin >> p[i].second; sort(p.begin(), p.end(), cmp); vector<int>g; for(int i = 0; i < n; i ++) { int x=p[i].second,y=p[i].first; if(H <= y || A <= x) continue; auto it=lower_bound(g.begin(),g.end(),x); if(it==g.end()) g.push_back(x); else *it=x; } cout << g.size() << '\n'; }
这个题目类似于背包问题，给定一组物品，每个物品有两个属性（重量和价值），以及两个整数H和A。要求在不超过背包容量H的情况下，尽可能多地选取物品放入背包，并且物品的价值必须大于等于A。输出满足条件的物品数量。
- 定义一个自定义类型
P，它是pair<int, int>的别名，用于存储物品的重量和价值。 - 定义比较函数
cmp，用于对物品按照“价值相同时优先选取重量大的”的原则进行排序。这里的排序是降序排列，因为在题目描述中并没有明确指出价值小的优先，但是根据实际情况，如果价值相等，应该选择重量大的。 - 输入整数n（物品数量）、H（背包容量）和A（物品价值下限）。
- 创建一个大小为n的
vector<P>容器p，存储每个物品的重量和价值。 - 依次读入每个物品的重量和价值，并存入容器p中。
- 对物品按照比较函数cmp定义的规则进行排序。
- 创建一个
vector<int>容器g，用于存储满足条件的物品重量。 - 遍历排序后的物品列表p，对于每个物品，检查其重量是否超过背包容量H或其价值是否低于阈值A。如果满足这两个条件之一，则跳过当前物品。
- 如果物品符合条件，则在容器g中查找第一个大于等于当前物品重量x的位置。这里使用了
lower_bound函数。 - 如果在g中找不到大于等于x的元素，则将x添加到g的末尾；如果找到了这样的元素，则替换该位置的元素为x。
- 遍历结束后，输出满足条件的物品数量，即g的大小。
- 怪物的血量（h）和攻击力（ai）可以看作是背包问题中的“物品”，每个怪物对应一个物品，物品的“价值”是击败怪物的数量（1个单位）。
- 小美的血量（H）和攻击力（A）可以理解为背包的“容量”，每次击败一个怪物后，小美的血量和攻击力都会变成被击败怪物的血量和攻击力，这意味着每次决策都会影响后续决策的可行性和收益。
- 由于血量和攻击力的变化特性，它并不完全符合常见的背包问题模型，而更像是一个带有状态转移约束的决策过程问题。
