MT3038 植发

简介: MT3038 植发

24e309f500a04e5487b01de99b07d936.jpg

0fd30343d2a34a979e7f0d026167d48e.jpg

思路:

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

先看点(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;
}


相关文章
|
5月前
|
人工智能 网络协议 Linux
MCP 协议: Streamable HTTP 是最佳选择
随着AI应用变得越来越复杂并被广泛部署,原有的通信机制面临着一系列挑战。近期MCP仓库的PR #206引入了一个全新的Streamable HTTP传输层替代原有的HTTP+SSE传输层。本文将详细分析该协议的技术细节和实际优势。
3070 100
|
JSON 文字识别 API
ocr表格识别返回的json结果,转成excel,这个转化有对应的逻辑代码吗?
ocr表格识别返回的json结果,转成excel,这个转化有对应的逻辑代码吗?
728 0
|
9月前
|
存储 NoSQL MongoDB
Redis在中国火爆,为何MongoDB更受欢迎国外?
本文介绍了Redis和MongoDB的基本概念及其在GitHub Star、DB-Engines Ranking和Google Trends中的数据对比。Redis是一个基于内存的键值对存储数据库,适合快速读写场景;MongoDB则是面向文档的数据库,支持大规模数据存储和复杂查询。全球范围内,MongoDB的搜索热度高于Redis,但在中国市场,Redis更受欢迎,因其高性能和低延迟特性满足了中国互联网公司对高并发的需求。总结部分分析了两者的特点及适用场景,并结合中美两国的行业背景解释了其受欢迎程度的不同原因。
289 1
|
JavaScript Java 测试技术
基于微信小程序的校园综合服务平台的设计与实现(源码+lw+部署文档+讲解等)
基于微信小程序的校园综合服务平台的设计与实现(源码+lw+部署文档+讲解等)
348 0
易优cms内核简洁文章资讯作文范文网站模板源码(带手机版)
易优cms内核简洁文章资讯作文范文网站模板源码(带手机版)
132 10
|
机器学习/深度学习 算法 数据挖掘
使用NumPy实现经典算法案例集
【4月更文挑战第17天】本文展示了NumPy在Python中实现经典算法的案例,包括使用NumPy进行冒泡排序、计算欧几里得距离、矩阵转置和协方差矩阵。这些示例突显了NumPy在数值计算、数据分析和科学计算中的威力,强调了掌握NumPy对于数据科学家和机器学习开发者的重要性。
|
存储 编译器 程序员
c++【继承】
C++ 继承,包括继承的概念和用法,菱形继承的产生,组合的介绍等丰富知识点,详细讲解,干货满满!
124 4
c++【继承】
|
JavaScript 前端开发 Java
学习Javascript闭包(Closure)
学习Javascript闭包(Closure)
81 0
|
开发工具 Docker Python
成功解决使用yum安装软件的时候提示/var/run/yum.pid被锁定
成功解决使用yum安装软件的时候提示/var/run/yum.pid被锁定
1695 0
成功解决使用yum安装软件的时候提示/var/run/yum.pid被锁定
|
JavaScript 前端开发 Java
图解 Google V8 # 06:原型链:V8是如何实现对象继承的?
图解 Google V8 # 06:原型链:V8是如何实现对象继承的?
201 0
图解 Google V8 # 06:原型链:V8是如何实现对象继承的?