题解：P1056 [NOIP2008 普及组] 排座椅

题目大意

给定

n

个坐标，要在一些地方开一条走道，使得被分开的坐标最多，其中横着

k

条，竖着

l

条。

题目分析

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

CPP

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

进行输入。

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

CPP

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++; //这条道路如果加上可以分开一个人
    }
}

排序找答案

找出分开人数多的道路。并且选定前

k

条，整理答案。

CPP

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);

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

CPP

#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;
}

点个赞吧！球球啦！

题解：P1056 [NOIP2008 普及组] 排座椅

文章操作

题目大意

题目分析

相关推荐

评论

题解：P1056 [NOIP2008 普及组] 排座椅