官方题解
2024-03-21 16:49:44
发布于:浙江
54阅读
0回复
0点赞
【算法分析】
本题的贪心需要预处理下,定义结构体 存当前位置和当前位置能隔开的对数,开 个结构体一维数组, 记录如果在第 行加通道,可以分割多少对调皮学生, 记录如果在第 列加通道,可以分割多少对调皮学生。
然后用 排序,隔开对数多的放在前面,在此前提下,位置小的排到前面(输出的结果也要排序)。
最后输出分割学生最多的前 行和前 列。
【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10;
struct Pos {
int pos, num; // 位置,隔开的对数
} row[N], col[N]; // 横向通道,纵向通道
bool cmp1(Pos a, Pos b) {
return a.num > b.num; // 隔开对数多的放前面
}
bool cmp2(Pos a, Pos b) {
return a.pos < b.pos; // 位置小的排在前面
}
int main() {
int m, n, k, l, d; // m 行 n 列的教室,k 个横向通道,l 个纵向通道,d 对交头接耳的同学
cin >> m >> n >> k >> l >> d;
for(int i = 1; i <= d; i++) {
int x1, y1, x2, y2; // 会交头接耳的两个同学的位置
cin >> x1 >> y1 >> x2 >> y2;
if(y1 == y2) { // 同一列
int x = min(x1, x2);
row[x].pos = x;
row[x].num++; // x 这条横向通道能隔开的对数加 1
}else if(x1 == x2) { // 同一行
int y = min(y1, y2);
col[y].pos = y;
col[y].num++; // y 这条纵向通道能隔开的对数加 1
}
}
sort(row + 1, row + m, cmp1); // 1~m-1
sort(col + 1, col + n, cmp1); // 1~n-1
sort(row + 1, row + k + 1, cmp2); // 1~k 按照位置升序
sort(col + 1, col + l + 1, cmp2); // 1~l 按照位置升序
for(int i = 1; i <= k; i++) {
cout << row[i].pos << " ";
}
cout << endl;
for(int i = 1; i <= l; i++) {
cout << col[i].pos << " ";
}
return 0;
}
【时间复杂度】
【预计得分】
这里空空如也
有帮助,赞一个