关注
大佬,这是我写的第三题,我没有参加笔试,看我写的对吗,单调队列维护这,
#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
相关推荐
07-08 10:56
安徽工程大学 运营 点赞 评论 收藏
分享

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 实习生的蛐蛐区 #
31002次浏览 225人参与
# 面试官是我前女友 #
106174次浏览 722人参与
# 计算机有哪些岗位值得去? #
10441次浏览 95人参与
# 说说你知道的学历厂 #
21983次浏览 134人参与
# 应届生,你找到工作了吗 #
16275次浏览 135人参与
# 你找工作的时候用AI吗? #
12419次浏览 135人参与
# 面试尴尬现场 #
18154次浏览 113人参与
# 电网笔面经互助 #
36079次浏览 351人参与
# 社会教会你的第一课 #
23972次浏览 300人参与
# 下班后的时间你怎么安排 #
5854次浏览 65人参与
# 哪一瞬间觉得自己长大了 #
5912次浏览 112人参与
# 你认为小厂实习有用吗? #
8693次浏览 92人参与
# 学历贬值真的很严重吗? #
21818次浏览 161人参与
# 职场中对你有帮助的书 #
17445次浏览 203人参与
# 简历当中有水分算不算造假? #
20653次浏览 245人参与
# 双非应该如何逆袭? #
188150次浏览 3408人参与
# 神州信息工作体验 #
15711次浏览 67人参与
# 哪些公司校招卡第一学历 #
61963次浏览 234人参与
# 现在前端的就业环境真的很差吗 #
294802次浏览 3571人参与
# 毕业旅行去哪玩儿 #
12336次浏览 133人参与