当前位置:网站首页>2022 Nioke Multi-School Training Session H Question H Take the Elevator
2022 Nioke Multi-School Training Session H Question H Take the Elevator
2022-08-05 00:23:00 【Rain Sure】
题目链接
题目大意
大概意思就是,Gave us a broken elevator,And some information about the passengers who need to take the elevator and the maximum capacity of the elevatorm.Ask us the minimum time required for the elevator to transport all passengers to the command floor.
题解
很明显的贪心题,但是不太好想,Here is an idea.
We consider ascending passengers and descending passengers separately,Because if the elevator starts to descend,Then it cannot go up any further;So we let the elevator go as high as possible every time you lie down,Then the time it takes for each trip is to take the largest one for ascending and descending;
主要实现方法:
Suppose the current moving range is [ l , r ] [l, r] [l,r],假设 l < r l < r l<r,Then the current is the upward direction,我们在 l l l处-1,在 r r r处+1,That is, into the elevator-1,出电梯+1; Then consider the highest point,The current highest point is the highest position the elevator will reach;
In the same way, consider the direction of descent:假设当前区间为 [ l , r ] [l, r] [l,r], l > r l > r l>r, l l l处-1, r r r处+1.Then sort all the points,Consider the highest position first,大概思路就是这样,细节看代码吧.
#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; // Rising and falling passengers are stored separately
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; // The maximum heights for ascent and descent are stored separately for each trip
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;
}
边栏推荐
- 2022 Hangzhou Electric Multi-School Training Session 3 1009 Package Delivery
- 软件测试面试题:软件测试类型都有哪些?
- redis可视化管理软件Redis Desktop Manager2022
- 元宇宙:未来我们的每一个日常行为是否都能成为赚钱工具?
- 2022杭电多校第三场 L题 Two Permutations
- 软件测试面试题:黑盒测试、白盒测试以及单元测试、集成测试、系统测试、验收测试的区别与联系?
- STC89C52RC的P4口的应用问题
- E - Many Operations (按位考虑 + dp思想记录操作后的结果
- 网站最终产品页使用单一入口还是多入口?
- Software testing interview questions: What is the difference between load testing, capacity testing, and strength testing?
猜你喜欢
性能测试如何准备测试数据
oracle创建用户
【论文笔记】—低照度图像增强—Unsupervised—EnlightenGAN—2019-TIP
QSunSync Qiniu cloud file synchronization tool, batch upload
node使用redis
论文解读( AF-GCL)《Augmentation-Free Graph Contrastive Learning with Performance Guarantee》
电子行业MES管理系统的主要功能与用途
在线中文姓名生成工具推荐
leetcode:266. 回文全排列
The master teaches you the 3D real-time character production process, the game modeling process sharing
随机推荐
tiup uninstall
【论文笔记】—低照度图像增强—Unsupervised—EnlightenGAN—2019-TIP
The master teaches you the 3D real-time character production process, the game modeling process sharing
canvas Gaussian blur effect
STC89C52RC的P4口的应用问题
软件测试面试题:做好测试计划的关键是什么?
软件测试面试题:关于自动化测试工具?
在线中文姓名生成工具推荐
找不到DiscoveryClient类型的Bean
【无标题】
TinyMCE禁用转义
gorm联表查询-实战
软件测试面试题:设计测试用例时应该考虑哪些方面,即不同的测试用例针对那些方面进行测试?
SV class virtual method of polymorphism
【idea】idea配置sql格式化
Three tips for you to successfully get started with 3D modeling
软件质量评估的通用模型
2022杭电多校第一场 1004 Ball
2022 The Third J Question Journey
[LeetCode] Summary of Matrix Simulation Related Topics