P3028 汽水机(差分)
2024-09-17 14:31:19
题目
P3028 [USACO10OCT]汽水机Soda Machine
解析
差分,看到\(a[i]\leq 1e9\),离散化一下,在\(l\)处\(+1\),\(r+1\)处\(-1\),这样就只有\(2n\)个点了,再按位置排一下序,扫一遍记录答案就可以了。
需要注意的是,如果在某个位置既有\(+1\)操作又有\(-1\)操作,要先\(-1\)再\(+1\),否则在统计答案的时候会多算
强化版
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int sum, ans, n;
struct node {
int pos, val;
bool operator<(const node & oth) const {
return pos == oth.pos ? val < oth.val : pos < oth.pos;
}
} e[N];
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1, x, y; i <= n; ++i) {
cin >> x >> y;
e[i] = (node) {x, 1}, e[i + n] = (node) {y + 1, -1};
}
sort(e + 1, e + 1 + n + n);
for (int i = 1; i <= n + n; ++i) {
sum += e[i].val;
ans = max(ans, sum);
}
cout << ans;
}
最新文章
- centos6.5下使用yum完美搭建LNMP环境(php5.6) 无脑安装
- h5上传图片及预览
- ASP.NET Web API自身对CORS的支持: EnableCorsAttribute特性背后的故事
- 【转】T-SQL 教程
- sql中having的使用
- 实例源码--Android底部功能分类Tab使用实例
- iOS OC语言: Block底层实现原理 (转载)
- java String对象的创建(jvm).
- chrome无法使用非官方商店扩展解决办法
- 利用svn自动同步更新到网站服务器 -- 网摘
- Java-老夫对泛型的理解。。
- 浅谈如何让 Bootstrap 3兼容IE8浏览器
- 在centos6,7 上编译安装内核
- C# Winform控件 - Form
- vue全选与取消全选
- 大数据 - hadoop三台linux虚拟服务器 - 初始化部署
- sql server 索引阐述系列四 表的B-Tree组织
- node中可读流、可写流
- 自定义MVC框架之工具类-图像处理类
- unable to find the sources of your current Linux kernel.
热门文章
- vm|vmware workstation 15|14 pro 激活|密钥|序列号|许可证
- UE4 C++中出现的让人手足无措的问题(持续更新)
- Java后端面经总结:拿下蚂蚁金服美团头条 offer 秘诀
- mysql的floor()报错注入方法详细分析
- vue中webpack的配置理解
- 201871010134-周英杰《面想对象程序设计(java)》第十一周学习总结
- 【Web】URL解析
- LeetCode 100. Same Tree相同的树 (C++)
- JDOJ 1162 是否闰年
- CF717A Festival Organization(第一类斯特林数,斐波那契数列)