题解 | 排座椅

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type Count struct {
	pos   int // 通道位置（行间或列间）
	count int // 隔开的说话对数量
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m, k, l, d int
	fmt.Fscanf(reader, "%d %d %d %d %d\n", &n, &m, &k, &l, &d)

	// 记录相邻行之间、相邻列之间的说话对数量
	rowGap := make([]int, n) // rowGap[i] 表示第 i 行和第 i+1 行之间的说话对数（i 从 0 到 n-2）
	colGap := make([]int, m) // colGap[j] 表示第 j 列和第 j+1 列之间的说话对数（j 从 0 到 m-2）

	for i := 0; i < d; i++ {
		var x, y, p, q int
		fmt.Fscanf(reader, "%d %d %d %d\n", &x, &y, &p, &q)

		// 统一为 0-indexed
		x--
		y--
		p--
		q--

		// 判断是否是上下相邻（同一列，行差1）
		if y == q {
			// 上下相邻，位于同一列
			rowGap[min(x, p)]++
		} else {
			// 左右相邻，位于同一行
			colGap[min(y, q)]++
        }
	}

	// 构建结构体用于排序
	var rowPairs, colPairs []Count
	for i := 0; i < n-1; i++ {
		if rowGap[i] > 0 {
			rowPairs = append(rowPairs, Count{i, rowGap[i]})
		}
	}
	for j := 0; j < m-1; j++ {
		if colGap[j] > 0 {
			colPairs = append(colPairs, Count{j, colGap[j]})
		}
	}

	// 降序排序
	sort.Slice(rowPairs, func(i, j int) bool {
		return rowPairs[i].count > rowPairs[j].count
	})
	sort.Slice(colPairs, func(i, j int) bool {
		return colPairs[i].count > colPairs[j].count
	})

	// 选择前 k 个行间通道位置（输出的是第 i+1 条通道在第 i+1 行之后）
	var hChannels []int
	for i := 0; i < k && i < len(rowPairs); i++ {
		hChannels = append(hChannels, rowPairs[i].pos+1) // 输出 1-indexed 行号
	}

	// 选择前 l 个列间通道位置
	var vChannels []int
	for i := 0; i < l && i < len(colPairs); i++ {
		vChannels = append(vChannels, colPairs[i].pos+1) // 输出 1-indexed 列号
	}

	// 递增排序
	sort.Slice(hChannels, func(i, j int) bool {
		return hChannels[i] < hChannels[j]
	})
	sort.Slice(vChannels, func(i, j int) bool {
		return vChannels[i] < vChannels[j]
	})

	// 输出横向通道（行间）
	for i := 0; i < len(hChannels); i++ {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(hChannels[i])
	}
	fmt.Println()

	// 输出纵向通道（列间）
	for i := 0; i < len(vChannels); i++ {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(vChannels[i])
	}
	fmt.Println()
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}