当前位置:网站首页>“蔚来杯“2022牛客暑期多校训练营2 H.Take the Elevator
“蔚来杯“2022牛客暑期多校训练营2 H.Take the Elevator
2022-07-30 22:48:00 【_Kiwi_Berry_】
题意:
一部电梯的容量为 m , 且下降的时候只有到了一楼才能转向。有 n 个人需要乘坐,每个人的起点终点分别为 li , ri 。问从一楼出发,满足所有乘客需求,最后回到一楼的最短时间。
思路:
将乘客的起始点终点相连,把起点和终点转化为左端点和右端点,把抽象成点,就成了类似区间覆盖的问题。
只是这里上楼下楼分开处理,不过两种情况做法基本就相同。因为下降时不能中途转向,我们肯定希望每次上升的高度尽可能低,而当前楼层最高的乘客我们是迟早要接到(送达)的。
故采用贪心算法,两种情况都按右端点从大往小排序,维护一个优先队列。对于每个点,先将优先队列中比当前右端点大的点pop掉,然后如果没满就加进去,否则等下一轮,将每一轮的最右端点 -1 存下。
最后对于两种情况排序后,不断取最大值*2,累加即可得到答案
Code:
#include <bits/stdc++.h>
// #define debug freopen("_in.txt", "r", stdin);
#define debug freopen("_in.txt", "r", stdin), freopen("_out.txt", "w", stdout);
typedef long long ll;
typedef unsigned long long ull;
typedef struct Node *bintree;
using namespace std;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll maxn = 1e6 + 10;
const ll maxm = 2e6 + 10;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-8;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
ll T, n, m, q, d, kase = 0;
ll arr[maxn];
struct Node
{
ll l, r;
bool operator<(Node other) const
{
if (r != other.r)
return r > other.r;
else
return l > other.l;
}
} nodes[4][maxn];
priority_queue<ll> que1, que2;
vector<ll> vec1, vec2;
void solve()
{
scanf("%lld%lld%lld", &n, &m,&q);
ll cnt1 = 0, cnt2 = 0;
for (ll i = 1; i <= n; i++)
{
ll l, r;
scanf("%lld%lld", &l, &r);
if (l > r)
{
nodes[1][++cnt1] = {
r, l};
}
else
{
nodes[2][++cnt2] = {
l, r};
}
}
sort(nodes[1] + 1, nodes[1] + 1 + cnt1);
sort(nodes[2] + 1, nodes[2] + 1 + cnt2);
ll wc = 0, zo = cnt2, now = 2;
while (zo > 0)
{
while(!que1.empty()) que1.pop();
ll num=zo;
vec2.push_back(nodes[now][1].r - 1);
que1.push(nodes[now][1].l);
num--;
for (ll i = 2; i <=zo; i++)
{
while (!que1.empty() && que1.top() >= nodes[now][i].r)
{
// printf("%lld %lld\n",que1.top(),nodes[now][i].r);
que1.pop();
}
if (que1.size() < m)
{
que1.push(nodes[now][i].l);
num--;
}
else
{
// printf("%lld %lld\n",nodes[now][i].l,nodes[now][i].r);
nodes[2-now][++wc]=nodes[now][i];
}
}
now=2-now;
wc=0;
zo=num;
}
// printf("1\n");
wc = 0, zo = cnt1, now = 1;
while(!que1.empty()) que1.pop();
while (zo > 0)
{
while(!que1.empty()) que1.pop();
ll num=zo;
vec1.push_back(nodes[now][1].r - 1);
que1.push(nodes[now][1].l);
num--;
for (ll i = 2; i <=zo; i++)
{
while (!que1.empty() && que1.top() >= nodes[now][i].r)
{
que1.pop();
}
if (que1.size() < m)
{
que1.push(nodes[now][i].l);
num--;
}
else
{
nodes[1-now][++wc]=nodes[now][i];
}
}
now=1-now;
wc=0;
zo=num;
}
ll sz1=vec1.size();
ll sz2=vec2.size();
// printf("%lld %lld\n",sz1,sz2);
sort(vec1.begin(),vec1.end());
sort(vec2.begin(),vec2.end());
ll ans=0;
while(sz1>0&&sz2>0)
{
ans+=max(vec1[sz1-1],vec2[sz2-1])*2;
sz1--;
sz2--;
}
// printf("%lld\n",ans);
while(sz1>0)
{
ans+=vec1[sz1-1]*2;
sz1--;
}
while(sz2>0)
{
ans+=vec2[sz2-1]*2;
sz2--;
}
printf("%lld\n",ans);
}
signed main()
{
// debug;
// scanf("%lld", &T);
T=1;
while (T--)
{
solve();
}
}
边栏推荐
猜你喜欢
EasyExcel comprehensive course combat
IJCAI2022教程 | 口语语言理解:最新进展和新领域
MySql 5.7.38下载安装教程 ,并实现在Navicat操作MySql
Golang go-redis cluster模式下不断创建新连接,效率下降问题解决
2022/07/30 学习笔记 (day20) 面试题积累
Apache Doris系列之:安装与部署详细步骤
IJCAI2022 Tutorial | Spoken Language Comprehension: Recent Advances and New Fields
WSL安装图形界面并通过xrdp/X-Launch访问
MySql统计函数COUNT详解
MySQL 5.7 detailed download, installation and configuration tutorial
随机推荐
OpenCV笔记(二十):滤波函数——filter2D
IDEA 连接 数据库
宁波中宁典当转让29.5%股权为283.38万元,2021年所有者权益为968.75万元
Rust编译报错:error: linker `cc` not found
详解操作符
[MySQL] Mysql transaction and authority management
Navicat cannot connect to mysql super detailed processing method
二进制序列
ZZULIOJ:1120: 最值交换
Go语学习笔记 - gorm使用 - gorm处理错误 Web框架Gin(十)
Solve npm warn config global `--global`, `--local` are deprecated. use `--location=global` instead
IDEA usage skills
IDEA使用技巧
MySql 5.7.38下载安装教程 ,并实现在Navicat操作MySql
cnpm的安装与使用
IJCAI2022 Tutorial | Spoken Language Comprehension: Recent Advances and New Fields
阿里云视频点播+项目实战
[MySQL] Related operations on databases and tables in MySQL
The problem of sticky packets in tcp protocol transmission
d违反常了吗