关注
大佬,这是我写的第三题,我没有参加笔试,看我写的对吗,单调队列维护这,
#include <bits/stdc++.h>
const int N = 1e5;
const int M = 1e9;
using namespace std;
typedef long long ll;
struct node
{
int x, val;
bool operator<(const node& n) const
{
return x < n.x;
}
}e[N];
int n,k; //数量和 范围
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> e[i].x >> e[i].val;
}
sort(e + 1, e + 1 + n);
deque<int> dq;
int sum = 0;
int max_ = 0;
for(int i = 1; i <= n; i++)
{
while(dq.size() && e[i].x - e[dq.front()].x > 2*k)
{
sum += max_;
dq.pop_front();
max_ = 0;
}
dq.push_back(i);
max_ = max(max_,e[i].val);
}
sum += max_;
cout << sum << endl;
}
查看原帖
点赞 1
相关推荐
点赞 评论 收藏
分享
卢来猴祖:别扯啥职业生涯,如果走开发连职业都找不到谈职业生涯还有什么意义,走测开也是不错的 点赞 评论 收藏
分享
01-11 08:47
门头沟学院 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客十周岁生日快乐 #
206988次浏览 1933人参与
# 你觉得什么岗位会被AI替代 #
34997次浏览 232人参与
# 我和mentor的爱恨情仇 #
101801次浏览 922人参与
# 一人一个landing小技巧 #
143275次浏览 1499人参与
# 如果工作一直消耗情绪还要继续做吗 #
18155次浏览 83人参与
# 四大天坑是哪四家? #
101841次浏览 235人参与
# 互联网公司评价 #
479975次浏览 4091人参与
# 机械人春招想让哪家公司来捞你? #
377885次浏览 3127人参与
# 聊聊你的被动加班经历 #
4985次浏览 81人参与
# 在国企工作的人,躺平了吗? #
392248次浏览 3951人参与
# 我的求职精神状态 #
422619次浏览 3075人参与
# 华为工作体验 #
289521次浏览 1376人参与
# 实习吐槽大会 #
405080次浏览 2168人参与
# 工作压力大怎么缓解 #
139037次浏览 1261人参与
# 找工作以来,你最看不惯__ #
18038次浏览 353人参与
# 你的mentor是什么样的人? #
49321次浏览 705人参与
# 第一次找实习,我建议__ #
69376次浏览 841人参与
# 实习教会我的事 #
52344次浏览 413人参与
# 实习怎么做才有更好的产出 #
14336次浏览 265人参与
# AI coding的好用工具分享 #
22158次浏览 411人参与
查看4道真题和解析