关注
大佬,这是我写的第三题,我没有参加笔试,看我写的对吗,单调队列维护这,
#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
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你想跟着什么样领导? #
5490次浏览 82人参与
# 什么样的背景能拿SSP? #
117273次浏览 410人参与
# 百度秋招 #
55962次浏览 394人参与
# 你的秋招白月光和意难平公司 #
7056次浏览 81人参与
# 分享一个让你热爱工作的瞬间 #
47428次浏览 412人参与
# 找实习是选平台还是选业务? #
10223次浏览 146人参与
# 从夯到拉,评价编程语言 #
5016次浏览 48人参与
# 秋招签约后的心态变化 #
106057次浏览 923人参与
# 职场吐槽大会 #
289718次浏览 2111人参与
# 每个月花钱最多的地方是? #
5272次浏览 76人参与
# xxx岗位的一天 #
10039次浏览 92人参与
# 作业帮求职进展汇总 #
77638次浏览 520人参与
# 十一月总结 #
13344次浏览 146人参与
# 你面试时吹过最大的牛 #
20230次浏览 116人参与
# 为什么国企只招应届生 #
218447次浏览 1262人参与
# 饿了么求职进展汇总 #
80264次浏览 684人参与
# 非技术求职现状 #
549498次浏览 3509人参与
# 实习学到最有价值的工作习惯 #
43611次浏览 378人参与
# 韶音科技求职进展汇总 #
64992次浏览 510人参与
# AI“智障”时刻 #
6037次浏览 54人参与
# 实习生如何通过转正 #
111737次浏览 1421人参与
深信服公司福利 790人发布