湫湫减肥越减越肥！ 最近，减肥失败的湫湫为发泄心中郁闷，在玩一个消灭免子的游戏。游戏规则很简单，用箭杀死免子即可。箭是一种消耗品，已知有M种不同类型的箭可以选择，并且每种箭都会对兔子造成伤害，对应的伤害值分别为Di（1 <= i <= >M），每种箭需要一定的QQ币购买。假设每种箭只能使用一次，每只免子也只能被射一次，请计算要消灭地图上的所有兔子最少需要的QQ币。Input输入数据有多组，每组数据有四行；第一行有两个整数N，M（1 <= N, M <= 100000），分别表示兔子的个数和箭的种类；第二行有N个正整数，分别表示兔子的血量Bi（1 <= i <= N）；第三行有M个正整数，表示每把箭所能造成的伤害值Di（1 <= i <= M）；第四行有M个正整数，表示每把箭需要花费的QQ币Pi（1 <= i <= M）。
特别说明：1、当箭的伤害值大于等于兔子的血量时，就能将兔子杀死；2、血量Bi，箭的伤害值Di，箭的价格Pi，均小于等于100000。Output如果不能杀死所有兔子，请输出”No”，否则，请输出最少的QQ币数，每组输出一行。Sample Input3 31 2 32 3 41 2 33 41 2 31 2 3 41 2 3 1Sample Output64
思路：每个箭只能用一次，而且“当箭的伤害值大于等于兔子的血量时，就能将兔子杀死”，所以这道题可以使用优先队列解决。为了避免伤害高的剑先将血量低的兔子杀死，所以应该先杀血量高的兔子，因此先将血量与伤害均从高到低排列：
bool cmp(int x, int y) {
return x > y;
}
bool cmp1(node x, node y) {
return x.a > y.a;
} sort(q + 1, q + 1 + n, cmp);
sort(sic + 1, sic + 1 + m, cmp1);随后，对兔子血量进行n次循环，循环中，将伤害大于血量的箭放入优先队列中。因在结构体中定义有
friend bool operator<(node c, node d) {//按b的大小排序，队列先进先出
return c.b > d.b;
}因此待所有满足的箭放入队列中后，取出队列顶，进行累加操作，n次循环结束后若可以杀死所有兔子即可输出结果。
注意：对sum进行累加的时候，不能将sum定义为int类型，可能会超出限制。
代码：
#include
#include
#include
using namespace std;
int q[100010], n, m;
struct node {
int a, b;
friend bool operator<(node c, node d) {//按b的大小排序，队列先进先出
return c.b > d.b;
}
}sic[100010];
bool cmp(int x, int y) {
return x > y;
}
bool cmp1(node x, node y) {
return x.a > y.a;
}
priority_queue
int main() {
int i, j;
while (~scanf_s("%d%d", &n, &m)) {
for (i = 1; i <= n; i++)
scanf_s("%d", &q[i]);
for (i = 1; i <= m; i++)
scanf_s("%d", &sic[i].a);
for (i = 1; i <= m; i++)
scanf_s("%d", &sic[i].b);
sort(q + 1, q + 1 + n, cmp);
sort(sic + 1, sic + 1 + m, cmp1);
if (n > m) {
printf("No\n"); continue;
}
while (!e.empty())
e.pop();
__int64 sum = 0;
j = 1;
for (i = 1; i <= n; i++) {
while (j <= m && sic[j].a >= q[i]) { //把满足击杀的箭放入优先队列
e.push(sic[j]);
j++;
}
if (e.empty())//队列空了，若此时i!=n，则有兔子无法被杀，直接跳出循环
break;
sum += e.top().b;
e.pop();
}
if (i != n + 1)
printf("No\n");
else
printf("%I64d\n", sum);
}
return 0;
}