当前位置:网站首页>2022牛客多校训练第二场 H题 Take the Elevator
2022牛客多校训练第二场 H题 Take the Elevator
2022-08-05 00:18:00 【Rain Sure】
题目链接
题目大意
大概意思就是,给了我们一部损坏的电梯,以及一些需要乘坐电梯的乘客的信息以及电梯的最大容量m。问我们电梯把所有乘客都运送到指令楼层所需要的最小时间。
题解
很明显的贪心题,但是不太好想,在这里给一个思路。
我们分别考虑上升的乘客和下降的乘客,因为电梯如果开始下降了,那么它就不能再上升了;所以我们让电梯每一躺尽可能走的高,那么每一趟所花费的时间就是上升的下降取一个最大的;
主要实现方法:
假设当前移动区间为 [ l , r ] [l, r] [l,r],假设 l < r l < r l<r,那么当前即为上升方向,我们在 l l l处-1,在 r r r处+1,也就是进电梯-1,出电梯+1; 然后考虑最高的点,当前最高的点即是电梯要到达的最高位置;
同理再考虑下降方向:假设当前区间为 [ l , r ] [l, r] [l,r], l > r l > r l>r, l l l处-1, r r r处+1.然后对所有点进行排序,先考虑最高的位置,大概思路就是这样,细节看代码吧。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
typedef struct node
{
int pos, type;
bool operator < (const struct node &w) const {
if(pos != w.pos) return pos > w.pos;
return type < w.type;
}
}Node;
vector<Node> up, down; // 分别存储上升和下降的乘客
int n, m, k;
signed main()
{
cin >> n >> m >> k;
for(int i = 0; i < n; i ++){
int a, b; cin >> a >> b;
if(a < b) {
up.push_back({
a, -1});
up.push_back({
b, 1});
}else{
down.push_back({
a, 1});
down.push_back({
b, -1});
}
}
vector<int> t1, t2; // 分别存储每一趟上升和下降的最大高度
sort(up.begin(), up.end());
sort(down.begin(), down.end());
int temp = 0;
for(auto item : up) {
temp += item.type;
if(temp > t1.size() * m) t1.push_back(item.pos);
}
temp = 0;
for(auto item : down) {
temp += item.type;
if(temp > t2.size() * m) t2.push_back(item.pos);
}
int res = 0;
for(int i = 0; i < t1.size() || i < t2.size(); i ++){
temp = 0;
if(i < t1.size()) temp = max(temp, t1[i]);
if(i < t2.size()) temp = max(temp, t2[i]);
res += (temp - 1) * 2;
}
cout << res << endl;
}
边栏推荐
猜你喜欢
随机推荐
Chinese and Japanese color style
关于我仔细检查审核过关于工作人员页面,返回一个所属行业问题
论文解读( AF-GCL)《Augmentation-Free Graph Contrastive Learning with Performance Guarantee》
How to burn the KT148A voice chip into the chip through the serial port and the tools on the computer
GO中sync包自由控制并发的方法
D - I Hate Non-integer Number (选数的计数dp
Three tips for you to successfully get started with 3D modeling
00、数组及字符串常用的 API(详细剖析)
MAUI Blazor 权限经验分享 (定位,使用相机)
软件测试面试题:LoadRunner 分为哪三个模块?
TinyMCE禁用转义
阅读笔记:如何理解DevOps?
uinty lua 关于异步函数的终极思想
MAUI Blazor 权限经验分享 (定位,使用相机)
MongoDB权限验证开启与mongoose数据库配置
电赛必备技能___定时ADC+DMA+串口通信
克服项目管理中恐惧心理
【unity编译器扩展之模型动画拷贝】
Flask框架 根据源码分析可扩展点
10 个关于 Promise 和 setTimeout 知识的面试题,通过图解一次说透彻