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

chrispang · 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;
}

点个赞吧！球球啦！