思路

• 关键性质：对任意人位置 $(x,y)$，对角线上出口 $(i,i)$ 的距离为 $|x-i|+|y-i|$。当 $i\in[\min(x,y),\max(x,y)]$ 时，有

且这是最小值。因此该人可选择的最近出口集合恰为整数区间

• 问题化为：给出 $m$ 个区间 $[L_j,R_j]$ 与点 $1,2,\ldots,n$（每点容量 $1$），最大化可将多少区间匹配到某个覆盖点。
• 最优解贪心：按点 $i=1\ldots n$ 扫描，维护一个按区间右端点 $R$ 的小根堆；当 $L\le i$ 时入堆，弹出所有 $R<i$ 的过期区间；若堆非空，则用点 $i$ 匹配当前 $R$ 最小的区间并弹出。该策略是区间调度/可并发单机调度的经典最优策略。
• 复杂度：排序后整体 $O((n+m)\log m)$，空间 $O(m)$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	if (!(cin >> n >> m)) return 0;
	vector<pair<int,int>> segs;
	segs.reserve(m);
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		int L = min(x, y), R = max(x, y);
		segs.emplace_back(L, R);
	}
	// 按左端点排序
	sort(segs.begin(), segs.end(), [](const auto& a, const auto& b){
		if (a.first != b.first) return a.first < b.first;
		return a.second < b.second;
	});
	
	priority_queue<int, vector<int>, greater<int>> pq; // 存右端点R
	long long ans = 0;
	int idx = 0;
	for (int i = 1; i <= n; ++i) {
		// 加入所有 L <= i 的区间
		while (idx < m && segs[idx].first <= i) {
			pq.push(segs[idx].second);
			++idx;
		}
		// 去掉已过期的区间
		while (!pq.empty() && pq.top() < i) pq.pop();
		// 用点 i 匹配 R 最小的区间
		if (!pq.empty()) {
			pq.pop();
			++ans;
		}
	}
	cout << ans << '\n';
	return 0;
}

Python

import sys
import heapq

def main():
	data = sys.stdin.buffer.readline().split()
	if not data:
		return
	n, m = map(int, data)
	segs = []
	for _ in range(m):
		x, y = map(int, sys.stdin.buffer.readline().split())
		L = x if x < y else y
		R = x if x > y else y
		segs.append((L, R))
	# 按 L 排序
	segs.sort()
	pq = []  # 小根堆存 R
	ans = 0
	idx = 0
	for i in range(1, n + 1):
		while idx < m and segs[idx][0] <= i:
			heapq.heappush(pq, segs[idx][1])
			idx += 1
		while pq and pq[0] < i:
			heapq.heappop(pq)
		if pq:
			heapq.heappop(pq)
			ans += 1
	print(ans)

if __name__ == "__main__":
	print = lambda x: sys.stdout.write(str(x))
	main()

Java

import java.io.*;
import java.util.*;

public class Main {
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		int nextInt() throws IOException {
			int c, sgn = 1, x = 0;
			do { c = read(); } while (c <= 32);
			if (c == '-') { sgn = -1; c = read(); }
			while (c > 32) {
				x = x * 10 + (c - '0');
				c = read();
			}
			return x * sgn;
		}
	}
	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		int n = fs.nextInt(), m = fs.nextInt();
		int[][] segs = new int[m][2];
		for (int i = 0; i < m; i++) {
			int x = fs.nextInt(), y = fs.nextInt();
			int L = Math.min(x, y), R = Math.max(x, y);
			segs[i][0] = L; segs[i][1] = R;
		}
		Arrays.sort(segs, (a, b) -> {
			if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
			return Integer.compare(a[1], b[1]);
		});
		PriorityQueue<Integer> pq = new PriorityQueue<>(); // 存R的小根堆
		long ans = 0;
		int idx = 0;
		for (int i = 1; i <= n; i++) {
			while (idx < m && segs[idx][0] <= i) {
				pq.offer(segs[idx][1]);
				idx++;
			}
			while (!pq.isEmpty() && pq.peek() < i) pq.poll();
			if (!pq.isEmpty()) {
				pq.poll();
				ans++;
			}
		}
		System.out.println(ans);
	}
}

题目内容

给定一个大小为几 $n×n$ 的迷宫，迷宫的单元格以坐标 $(x,y)$ 表示，其中 $1≦x,y≦n$ 。

在迷宫中有 $m$ 个人，每个人初始位于坐标 $(x_i,y_i)$ 。他们每一步可以移动到一个与当前位置四相邻的单元格。

在坐标 $(i,i)(1≦i≦n)$ 的位置上有 $n$ 个出口。每个出口只能使用一次，当有人在该出口逃出迷宫后，该出口即刻关闭。

每个人会选择离自己最近的出口(最小曼哈顿距离)作为逃生终点。若存在多个最近的出口，人员之间会协调分配，以使最终逃出的人数最大化。

当所有人按照上述规则前往各自目标出口后，计算最终有多少人能够成功逃出迷宫。

【名词解释】

• 四相邻：四相邻 是指当 $|x-x'|+|y-y'|=1$ 时，单元格 $(x,y)$ 与 $(x',y')$ 被认为相邻的，可以在一步中相互移动。

• 曼哈顿距离：两个点 $(x_1,y_1),(x_2,y_2)$ 之间的曼哈顿距离为他们横坐标加纵坐标差，即 $|x_1-x_2|+|y_1-y_2|$

输入描述

第一行输入两个整数 $n$ 和 $m(2≦n,m≦10^6)$ ，分别表示迷宫的边长与人的数量。

接下来 $m$ 行，每行输入两个整数 $x_i$ 和 $y_i$ $(1≦x_i,y_i≦n)$ ，表示第 $i$ 个人的初始坐标。

输出描述

输出一个整数，表示最终能够逃出迷宫的人的数量。

样例1

输入

2 3
1 2
2 1
1 1

输出

2

说明

在这个样例中：

• 迷宫有 $2$ 个出口，分别位于 $(1,1)$ 和 $(2,2)$；

• $3$ 位人分别位于 $(1,2),(2,1),(1,1)$ ；

• 每个出口只能使用一次，所以最多有 $2$ 个出口被使用，因此共有 $2$ 人逃出。

样例2

输入

4 3
1 2
1 2
1 2

输出

2

说明

在这个样例中：

• 迷宫有 $4$ 个出口，分别位于 $(1,1),(2,2),(3,3),(4,4)$ ；

• $3$ 位人分别位于 $(1,2)$ ，距离出口的距离为 $1,1,3,5$

• 他们三人都只会选择 $(1,1),(2,2)$ 的出口，因出口有人进入后会关闭所以三人中只有两个人能逃出。

• 出口 $(3,3)$ 和 $(4,4)$ 未被使用，因为它们并非任何人的最近出口(距离为 $3,5$ ) 。