【每日一题】8月10日题目精讲—排座椅
排座椅
https://ac.nowcoder.com/acm/problem/16618
题目：https://ac.nowcoder.com/acm/problem/16618
思路：分开行与列分开计算，贪心即可，记得存一下位置并且输出顺序
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<queue>
#include<bits/stdc++.h>
typedef long long ll;
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a* b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
int qmi(int a, int k, int p) //快速幂模板
{
int res = 1;
while (k)
{
if (k & 1) res = (ll)res * a % p;
k >>= 1;
a = (ll)a * a % p;
}
return res;
}
///////////////////////////////////////////////////////////
int ax[N]; int by[N];//存储说话位置数组
int ans1[N], ans2[N];//输出答案数组
struct node {
int cnt;
int pos;
}p[N],q[N];
bool cmp(node a, node b) {
return a.cnt > b.cnt;
}
int main()
{
int M, N, K, L, D;
cin >> M >> N >> K >> L >> D;
memset(ax, 0, sizeof(ax));
memset(by, 0, sizeof(by));
for (int i = 1; i <= D; i++) {
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 == x2) {//当两个人是横着说话时
int minn = min(y1, y2);
by[minn]++;
}
else {//当两个人是竖着说话时
int minn = min(x1, x2);
ax[minn]++;
}
}
for (int i = 1; i <= M; i++) {
if (ax[i]) {
p[i].cnt = ax[i];
p[i].pos = i;
}
}
for (int i = 1; i <= N; i++) {
if (by[i]) {
q[i].cnt = by[i];
q[i].pos = i;
}
}
sort(q + 1, q + 1 + N, cmp);
sort(p + 1, p + 1 + M, cmp);
for (int i = 1; i <= K; i++) {
ans1[i] = p[i].pos;
}
for (int i = 1; i <= L; i++) {
ans2[i] = q[i].pos;
}
sort(ans1 + 1, ans1 + 1 + K);
sort(ans2 + 1, ans2 + 1 + L);
for (int i = 1; i <= K; i++) {
cout << ans1[i] << " ";
}
cout << endl;
for (int i = 1; i <= L; i++) {
cout << ans2[i] << " ";
}
cout << endl;
return 0;
}
/*
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
*/
