MT3038 植发

admin2024-05-15  1

MT3038 植发,第1张

 MT3038 植发,第2张思路:

有两个点可以取头发,每个头发寿命不同。

先看点(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;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!