题目内容:比基堡海滩有一个有n个触手的恐怖水母,蟹老板希望雇佣一些海绵宝宝把它杀死(即砍掉所有触手)。现在有m个海绵宝宝可以雇佣,一个能力值为x的海绵宝宝可以砍掉恐怖水母一只直径不超过x的触手,且需要支付x个金币。如何雇佣海绵宝宝才能杀死水母,并且支付的金币最少?需要注意一个海绵宝宝只能砍掉一只触手,并且不能被雇佣两次。 输入格式:第1行为正整数n和m,第2行为水母n只触手的直径,第3行为m个海绵宝宝的能力值,所有数据用空格间隔。 输出格式:输出最少金币数。如果无解,输出NULL 输入样例: 2 3 5 4 7 8 4 输出样例: 11 C++
时间: 2024-02-12 15:03:56 浏览: 164
这是一个贪心算法的问题,可以按照以下思路解决:
1. 读入整数 n 和 m;
2. 读入 n 个整数表示恐怖水母的触手直径;
3. 读入 m 个整数表示海绵宝宝的能力值;
4. 将恐怖水母的触手直径从小到大排序;
5. 将海绵宝宝的能力值从小到大排序;
6. 对于每个触手,找到能力值最小的海绵宝宝,把它雇佣来砍掉这个触手;
7. 如果找不到能力值大于等于触手直径的海绵宝宝,则无解。
具体实现代码如下:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int a[N], b[N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
cin >> b[i];
}
sort(a, a + n);
sort(b, b + m);
int res = 0;
for (int i = 0, j = 0; i < n; i++) {
while (j < m && b[j] < a[i]) j++;
if (j == m) {
cout << "NULL" << endl;
return 0;
}
res += b[j];
j++;
}
cout << res << endl;
return 0;
}
```
输入样例:
```
2 3
5 4
7 8 4
```
输出样例:
```
11
```
阅读全文
相关推荐
![docx](https://img-home.csdnimg.cn/images/20241231044901.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231044930.png)
![-](https://img-home.csdnimg.cn/images/20241231044937.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)