[NOIP2008]排座椅

第一行，有 5 各用空格隔开的整数，分别是 $M，N，K，L，D（2 ≤ N，M ≤ 1000，0 ≤ K < M，0 ≤ L < N，D ≤ 2000）$ 。
接下来 $D$ 行，每行有 4 个用空格隔开的整数，第 $i$ 行的 4 个整数 $X_i，Y_i，P_i，Q_i$ ，表示坐在位置 $(X_i,Y_i)$ 与 $(P_i,Q_i)$ 的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

输入数据保证最优方案的唯一性。

共两行

第一行包含 $K$ 个整数， $a_1a_2……a_K$ ，表示第 $a_1$ 行和 $a_1+1$ 行之间、第 $a_2$ 行和第 $a_2+1$ 行之间、…、第 $a_K$ 行和第 $a_K+1$ 行之间要开辟通道，其中 $a_i < a_{i+1}$ ，每两个整数之间用空格隔开（行尾没有空格）。
第二行包含 $L$ 个整数， $b_1b_2……b_k$ ，表示第 $b_1$ 列和 $b_1+1$ 列之间、第 $b_2$ 列和第 $b_2+1$ 列之间、…、第 $b_L$ 列和第 $b_L+1$ 列之间要开辟通道，其中 $b_i< b_{i+1}$ ，每两个整数之间用空格隔开（行尾没有空格）。

pypy3(pypy3.6.1) 解法, 执行用时: 81ms, 内存消耗: 22840K, 提交时间: 2020-09-01 03:17:49

#!/usr/bin/env python3
#
# 排座椅
#
import sys, os

def read_ints(): return list(map(int, input().split()))

m, n, k, l, d = read_ints()
r = [[0, i] for i in range(m - 1)]
c = [[0, i] for i in range(n - 1)]
for _ in range(d):
	x1, y1, x2, y2 = read_ints()
	x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
	if x1 == x2: c[min(y1, y2)][0] += 1
	elif y1 == y2: r[min(x1, x2)][0] += 1

r.sort(key=lambda x: -x[0])
c.sort(key=lambda x: -x[0])
ans1, ans2 = [], []
for i in range(k): ans1.append(r[i][1] + 1)
for i in range(l): ans2.append(c[i][1] + 1)

print(" ".join(map(str, sorted(ans1))))
print(" ".join(map(str, sorted(ans2))))

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 436K, 提交时间: 2022-10-13 22:19:35

#include<bits/stdc++.h>
using namespace std;
int x[1005]={0},y[1005]={0},jx[1005]={0},jy[1005]={0},m,n,k,l,d,i,p,q,a,b;
int main(){
    cin>>m>>n>>k>>l>>d;
    for(i=1;i<=d;i++){
        cin>>p>>q>>a>>b;
        if(p==a){x[min(q,b)]+=1;jx[min(q,b)]+=1;}
        if(q==b){y[min(p,a)]+=1;jy[min(p,a)]+=1;}
    }
    sort(x+1,x+n+1),sort(y+1,y+m+1);
    int s=0;
    for(i=1;i<=m;i++) if(jy[i]>y[m-k]){cout<<i;s++;if(s<k)cout<<' ';}
    s=0;
    cout<<'\n';
    for(i=1;i<=n;i++) if(jx[i]>x[n-l]){cout<<i;s++;if(s<l)cout<<' ';}
    return 0;
}

Python3(3.5.2) 解法, 执行用时: 24ms, 内存消耗: 3800K, 提交时间: 2020-08-10 22:47:51

from collections import defaultdict
n, m, k, l, d = map(int, input().split())
row = defaultdict(int)
line = defaultdict(int)
for i in range(d):
    x, y, p, q = map(int, input().split())
    if x == p:
        line[min(y, q)] += 1
    else:
        row[min(x, p)] += 1
ar = sorted(row, key=lambda z: -row[z])[:k]
ar.sort()
al = sorted(line, key=lambda z: -line[z])[:l]
al.sort()
print(' '.join(map(str, ar)))
print(' '.join(map(str, al)))

详情