自动搬运

查看原文

来自洛谷，原作者为

	chrispang 菜就是菜，怎么练都没用！|| 支持互关，规则见主页 || 禁止发接龙，发过来我会发回去 || 小号 1822435

搬运于2025-08-24 21:20:25，当前版本为作者最后更新于2025-01-18 16:06:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定 $n$ 个坐标，要在一些地方开一条走道，使得被分开的坐标最多，其中横着 $k$ 条，竖着 $l$ 条。

题目分析

1. 我们定义一个结构体，表示一条道路的坐标和可以分开的人数。之后定义 $x$ 数组和 $y$ 数组表示横着的道路与竖着的道路。

struct node{
	int x, n; //x表示分开的行或列，n表示分开的人数 
}x[1010], y[1010];

2. 进行输入。

我们使用我们的结构体记录一条道路分开后能分开几个人，之后处理答案。

cin >> m >> n >> k >> l >> d;
for (int i = 1; i <= d; i++) {
	int x1, y1, p1, q1;
	cin >> x1 >> y1 >> p1 >> q1;
	if(x1 == p1) {
		y[min(y1, q1)].x = min(y1, q1); //记录坐标 
		y[min(y1, q1)].n++; //这条道路如果加上可以分开一个人
	}
    if(y1 == q1) {
	    x[min(x1, p1)].x = min(x1, p1); //记录坐标
	    x[min(x1, p1)].n++; //这条道路如果加上可以分开一个人
    }
}

3. 排序找答案

找出分开人数多的道路。并且选定前 $k$ 条，整理答案。

bool cmp1(node a, node b) { //按人数排
	return a.n > b.n;
}

bool cmp2(node a, node b) { //按坐标排
	return a.x < b.x;
}

sort(x + 1, x + 1 + 1000, cmp1); //分开人数多的放前面
sort(y + 1, y + 1 + 1000, cmp1);
sort(x + 1, x + 1 + k, cmp2); //整理答案 
sort(y + 1, y + 1 + l, cmp2);

最后，放上我们的完整代码！

#include<bits/stdc++.h>
using namespace std;

int m, n, k, l, d;
struct node{
	int x, n; //x表示分开的行或列，n表示分开的人数 
}x[1010], y[1010];

bool cmp1(node a, node b) {
	return a.n > b.n;
}

bool cmp2(node a, node b) {
	return a.x < b.x;
}

int main() {
	cin >> m >> n >> k >> l >> d;
	for (int i = 1; i <= d; i++) {
		int x1, y1, p1, q1;
		cin >> x1 >> y1 >> p1 >> q1;
		if(x1 == p1) {
			y[min(y1, q1)].x = min(y1, q1); //记录坐标 
			y[min(y1, q1)].n++; //这条道路如果加上可以分开一个人
		}
		if(y1 == q1) {
			x[min(x1, p1)].x = min(x1, p1); //记录坐标
			x[min(x1, p1)].n++; //这条道路如果加上可以分开一个人
		}
	}
	sort(x + 1, x + 1 + 1000, cmp1); //分开人数多的放前面
	sort(y + 1, y + 1 + 1000, cmp1);
	sort(x + 1, x + 1 + k, cmp2); //整理答案 
	sort(y + 1, y + 1 + l, cmp2);
	for (int i = 1; i <= k; i++)
		cout << x[i].x << " ";
	cout << endl;
    for (int i = 1; i <= l; i++)
		cout << y[i].x << " ";
	return 0;
}

点个赞吧！球球啦！