排座椅

排座椅

思路

直接贪心，看哪个位置隔开得人多就在这个地方开一条路，所以我们只要统计一下每条道路隔开得人数，然后按照这个作为关键字，从大到小排序，然后就可以得到我们得答案了。

代码

/*
  Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back
#define endl '\n'
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')    f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

const int N = 1e3 + 10;

int num1[N], num2[N];

vector<pii> a, b;

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int m = read(), n = read(), k = read(), l = read(), d = read();
    for(int i = 1; i <= d; i++) {
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        if(x1 == x2) num2[min(y1, y2)]++;
        else num1[min(x1, x2)]++;
        //用了两个桶来记录 行 和 列 隔开的人数
    }
    //用pair<int, int> 来记录状态，主要是懒，不想写结构体，，，
    for(int i = 1; i <= m; i++) {
        if(num1[i]) a.pb(mp(num1[i], i));
    }
    for(int i = 1; i <= n; i++) {
        if(num2[i]) b.pb(mp(num2[i], i));
    }
    sort(a.begin(), a.end(), greater<pii>());//按照第一关键字降序。
    sort(b.begin(), b.end(), greater<pii>());
    vector<int> ans1, ans2;//因为上面的答案可能是无序的，所以先统计下来，然后再排序输出。
    for(int i = 0; i < k; i++) {
        ans1.pb(a[i].second);
    }
    for(int i = 0; i < l; i++) {
        ans2.pb(b[i].second);
    }
    sort(ans1.begin(), ans1.end());
    sort(ans2.begin(), ans2.end());
    for(int i = 0; i < k; i++)
        printf("%d%c", ans1[i], i + 1 == k ? '\n' : ' ');
    for(int i = 0; i < l; i++)
        printf("%d%c", ans2[i], i + 1 == l ? '\n' : ' ');
    return 0;
}