题目背景:
你作为一个村的村长,保卫村庄是理所当然的了。今天,村庄里来了一只恶龙,他有 n 个头,恶龙到处杀人放火。你着急了。不过天无绝人之路,现在来了一个骑士团。里面有 m 位成员(往下看)。
题目描述:
每个人都可以砍掉至多一个大小不超过x的头,需要 i个金币,求最小花费。
输入格式
第一行两个整数 n,m。
下接 n行,一个整数表示 n 个头的大小。
下接 m 行,每个人可以砍的头大小和需要的金币数
输出格式:
一个整数,最小花费。如果无解,输出 you died!。
思路😗:
*贪心思想,把每一个恶魔从头小到大排序,骑士的钱随着能力的提高而提高,因此
我们用尽可能的避免"杀鸡用牛刀"浪费钱的情况,可以用优先队列方便排序,与此相对于素组而言更方便杀死了的恶魔的去处以及雇佣完了的骑士和能力不足的骑士踢出队伍.
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 105000;
bool st;
long long n, m, sum1, sum2, sum, k;
int x, y;
priority_queue<int, vector<int>, greater<int>>e;//恶魔
priority_queue<int, vector<int>, greater<int>>q;//骑士
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)//输入恶魔
{
cin >> x;//恶魔的头的大小
e.push(x);//放入队列
}
for (int i = 1; i <= m; i++)//输入骑士的杀敌数
{
cin >> y;//每一个骑士的能力
q.push(y);//放入队列
}
if (n > m)//先特判一种绝对打不过的情况
{
cout << "you died!";
return 0;
}
while (e.size())//只要恶魔没有被除干净就不会跳出循环
{
if (e.size() && !q.size())//骑士没了,但是仍然有恶魔
//判断出来提前退出循环的条件
{
cout << "you died!";
return 0;//退出
}
if (e.top() <= q.top())//只要这个小骑士的能力够
{
sum += q.top();//雇佣这个小骑士
e.pop();//恶魔死了,去掉
q.pop();//骑士杀完了恶魔,因为只能杀一个,去掉
}
else q.pop();//如果这个小骑士能力不足,直接踢出去换人
}
cout << sum;//输出结果
return 0;
}