题意:行
列小孩,给定
个横向分界线和
个纵向分界线,总共有
对小孩会交头接耳,问将这些分界线放在什么地方会使得交头接耳的小孩尽可能少。
数据范围:
题解:
乍一看数据范围还以为是,分析完后横向和纵向相互独立,没有影响。
所以每个方向单独考虑即可。即统计交头接耳的小孩的数量然后从大到小排序即可。
注意输出的时候先输出横向分界线和纵向分界线,且要按照分界线的序号大小来输出。
即先统计出来所有的分界线,然后按照其编号大小输出。
代码:
#include<bits/stdc++.h> using namespace std; const int N = 1010; struct Node{ int id, cnt; bool operator < (const Node &A) const { return cnt > A.cnt; } }x[N], y[N]; int ans[N]; int n, m, K, L, D; int main() { scanf("%d%d%d%d%d", &n, &m, &K, &L, &D); for(int i = 1; i <= max(n, m); i++) x[i] = y[i] = {i, 0}; for(int i = 1; i <= D; i++) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); if(a == c) ++y[min(b, d)].cnt; else ++x[min(a, c)].cnt; } sort(x + 1, x + 1 + n); for(int i = 1; i <= K; i++) ans[i] = x[i].id; sort(ans + 1, ans + 1 + K); for(int i = 1; i <= K; i++) printf("%d%c", ans[i], " \n"[i == K]); sort(y + 1, y + 1 + m); for(int i = 1; i <= L; i++) ans[i] = y[i].id; sort(ans + 1, ans + 1 + L); for(int i = 1; i <= L; i++) printf("%d%c", ans[i], " \n"[i == L]); return 0; }