植物大战僵尸这款游戏中,有一种植物武器叫辣椒炸弹,在草坪中的任意一格摆放它可以把草坪中该行上的所有僵尸瞬间消灭,也就是说,如果在第i行中任意位置摆放一个炸弹,第i行中的所有僵尸就瞬间都被杀死了。现在我们假定草坪有r行c列,草坪中有n只僵尸,僵尸不移动,现在给你k个樱桃炸弹,要求只能使用这k个炸弹来消灭这些僵尸,请问最多可以杀死多少只僵尸。 【输入格式】 第一行4个正整数r,c,k,n; 接下来n行,每行两个正整数x,y,表示第x行的第y列中有一只僵尸。 【输出格式】 第一行输出最多可以杀死的僵尸数; 第二行按顺序输出所有被消灭的行,如果有不同方案,输出字典序最小的那种方案。 c++代码
时间: 2023-11-04 07:05:41 浏览: 120
```c++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int r, c, k, n;
vector<int> row[N]; // row[i] 表示第i行有哪些僵尸
int cnt[N]; // cnt[i] 表示第i行有几只僵尸
bool cmp(int a, int b)
{
return cnt[a] > cnt[b];
}
int main()
{
cin >> r >> c >> k >> n;
for (int i = 0; i < n; i ++ )
{
int x, y;
cin >> x >> y;
row[x].push_back(y);
cnt[x] ++ ;
}
vector<int> rows;
for (int i = 1; i <= r; i ++ ) rows.push_back(i); // rows 存储所有行号
sort(rows.begin(), rows.end(), cmp); // 按每行僵尸数量排序
int res = 0; // 最多可以杀死的僵尸数
vector<int> ans; // 存储被消灭的行
for (int i = 0; i < k; i ++ )
{
if (rows.empty()) break; // 行已经全部消灭
int rowId = rows.front();
int cntZombies = cnt[rowId]; // 当前行有多少僵尸
res += cntZombies;
ans.push_back(rowId);
rows.erase(rows.begin()); // 删除当前行
for (auto col: row[rowId]) // 将当前行中的僵尸所在列上的所有行的僵尸数减1
{
for (int j = max(1, rowId - 1); j <= min(r, rowId + 1); j ++ ) // 枚举与当前行相邻的行
{
auto it = find(row[j].begin(), row[j].end(), col); // 查找该列上是否有僵尸
if (it != row[j].end()) // 如果找到了
{
cnt[j] -- ; // 改变该行的僵尸数
row[j].erase(it); // 删除该行上该僵尸
}
}
}
}
cout << res << endl;
sort(ans.begin(), ans.end());
for (auto x: ans) cout << x << ' ';
cout << endl;
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)