思路：
有两个点可以取头发，每个头发寿命不同。
先看点(0,0)，按寿命由小到大排序（先考虑寿命短的可以移植到哪里）。
(0,0)点头发放置的位置应该让(0,m)点的头发可以尽可能多的放置（例如(0,0)点有一根头发既可以放置在(1,5)点，又可以放置在(5,1)点，则会放置在(1,5)点）
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e4 + 10; struct node { int x, y; int dis; bool operator<(const node &a) const { // 大根堆,重载<号 return dis < a.dis; } }; int a1[N], a2[N]; // 不同寿命头发有多少根 int n, m, k, l; bool used[N][N]; vector<pair<int, int>> s1[N], s2[N]; // 存储不同距离下的点的坐标 priority_queue<node> down, up; // 大根堆 down 和 up int dist(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2); } int main() { cin >> n >> m; cin >> k; for (int i = 0; i < k; i++) { //(0,0)处头发 int x; cin >> x; a1[x]++; // 存寿命为x的头发有多少根 } cin >> l; for (int i = 0; i < l; i++) { //(0,m)处头发 int x; cin >> x; a2[x]++; } for (int i = 1; i <= n; i++) { // 对于每一个点，都计算离(0,0)和(0,m)的距离 for (int j = 1; j <= m; j++) { // s1s2存不同距离下有哪些点 s1[dist(i, j, 0, 0)].push_back({i, j}); s2[dist(i, j, 0, m + 1)].push_back({i, j}); } } int flag = 0; // 先看离(0,0)的距离 for (int i = 1; i <= n + m; i++) { // 遍历每一个距离 (i不仅为距离，还为要消耗的寿命) for (int j = 0; j < s1[i].size(); j++) { // 对于指定的距离，把符合的点放到队列里 int x = s1[i][j].first; int y = s1[i][j].second; node tmp; tmp.dis = dist(x, y, 0, m + 1), tmp.x = x, tmp.y = y; down.push(tmp); } for (int j = 0; j < a1[i]; j++) { // 对于同一个寿命，可以放的位置 if (down.empty()) { //(0,0)的头发已放完 flag = 1; break; } // 取出能放的最远的点 int tmpx = down.top().x; int tmpy = down.top().y; down.pop(); used[tmpx][tmpy] = 1; // 记录该位置已被使用 } if (flag == 1) { break; } } // 先看离(0,m)的距离 for (int i = 1; i <= n + m; i++) { // 遍历每一个距离i for (int j = 0; j < s1[i].size(); j++) { int x = s2[i][j].first; int y = s2[i][j].second; if (used[x][y] == 1) { // 若该位置已经被使用，跳过 continue; } node tmp; tmp.dis = dist(x, y, 0, 0), tmp.x = x, tmp.y = y; up.push(tmp); } for (int j = 0; j < a2[i]; j++) { if (up.empty()) { flag = 1; break; } int tmpx = up.top().x; int tmpy = up.top().y; up.pop(); used[tmpx][tmpy] = 1; } if (flag == 1) { break; } } if (flag == 0) cout << "YES"; else cout << "NO"; return 0; }
