P2695 骑士的工作题解

旅行传送门：P2695 骑士的工作 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

你作为一个村的村长，保卫村庄是理所当然的了.今天，村庄里来了一只恶龙，他有n个头，恶龙到处杀人放火。你着急了。不过天无绝人之路，现在来了一个骑士团。里面有m位成员（往下看）

题目描述

每个人都可以砍掉一个大小不超过（<=）z的头，要money个金币，求最小花费。

输入格式

第一行两个整数 n m

下接n行，一个整数表示n个头的大小。

下接m行，每个人可以砍的头大小或金币(金币==头的大小）。

输出格式

一个整数，最小花费。如果无解，输出“you died!”

输入输出样例

输入 #1

输出 #1

说明/提示

1<=n,m<=20000

解题思路

很久很久以前，巨龙突然出现~

用两个优先队列分别维护头的大小和每个人可以砍的头的大小，即保证花最少的钱砍最小的头。如果当前成员不能砍掉队列最前端的头（即最小的头），那说明他也不可能砍掉之后的头，（既然如此就没有存在的必要了，毁灭吧赶紧的）；而如果可以砍掉，每个人也只能砍一个头，所以不管能不能砍掉，都需要pop当前成员换下一位。当成员队列为空而头队列不为空时，说明无解，否则输出最小花费。

AC代码

 1 #include <bits/stdc++.h>
 2 #define MAXN 20000 + 10
 3 
 4 using namespace std;
 5 
 6 int read()
 7 {
 8     int x = 0, f = 1;
 9     char ch = getchar();
10     while (ch < '0' || ch > '9')
11     {
12         if (ch == '-')
13             f = -1;
14         ch = getchar();
15     }
16     while (ch >= '0' && ch <= '9')
17     {
18         x = x * 10 + ch - '0';
19         ch = getchar();
20     }
21     return x * f;
22 }
23 
24 int main(int argc, char const *argv[])
25 {
26     int n = read(), m = read(), money = 0, temp;
27     priority_queue<int, vector<int>, greater<int>> heads;
28     priority_queue<int, vector<int>, greater<int>> humen;
29     for (int i = 0; i < n; i++)
30     {
31         temp = read();
32         heads.push(temp);
33     }
34     for (int i = 0; i < m; i++)
35     {
36         temp = read();
37         humen.push(temp);
38     }
39     while (!humen.empty())
40     {
41         if (heads.empty())
42             break;
43         if (humen.top() >= heads.top())
44         {
45             //如果当前成员能砍掉最前端的头，则加上当前成员的花费。
46             money += humen.top();
47             heads.pop();
48         }
49         humen.pop();
50     }
51     if (!heads.empty())
52         puts("you died!");
53     else
54         printf("%d\n", money);
55     return 0;
56 }

View Code

P2695 骑士的工作 题解