本文主要是介绍MT3038 植发，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：
有两个点可以取头发，每个头发寿命不同。
先看点(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++){ // 遍历每一个距离ifor (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";elsecout << "NO";return 0;
}这篇关于MT3038 植发的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
