HDU 6119 小小粉丝度度熊 双指针
2024-10-19 16:41:03
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6119
题意:中文题面。
解法:先处理可能交叉的区间,然后容易发现满足双指针的特性。
//HDU 6119
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
const int maxn = 1e5+10;
pair<LL,LL>p[maxn];
LL n,m,sum[maxn]; int main()
{
while(~scanf("%lld%lld",&n,&m))
{
for(int i=1; i<=n; i++) scanf("%lld%lld",&p[i].first,&p[i].second);
sort(p+1,p+n+1);
int cnt=0;
for(int i=1; i<=n; i++){
LL l=i,r=i+1,last=p[i].second;
while(r<=n&&p[r].first<=last){
last=max(last,p[r].second),r++;
}
r--;
p[cnt++]=make_pair(p[l].first,last);
i=r;
}
sum[0]=0;
for(int i=1; i<cnt; i++){
sum[i]=sum[i-1]+p[i].first-p[i-1].second-1;
}
LL ans=m;
int r=0;
for(int l=0; r<cnt&&l<cnt; l++){
while(sum[r]-sum[l]<=m&&r<cnt) r++;
LL x = m-(sum[r-1]-sum[l]);
ans = max(ans, p[r-1].second-p[l].first+1+x);
}
printf("%lld\n", ans);
}
return 0;
}
最新文章
- Canvas基础认识
- jquery this 和 event.target 区别
- CSS之viewport 1
- Linux系统下安装MongoDB 指南
- 用c#开发微信 (12) 微统计 - 阅读分享统计系统 2 业务逻辑实现
- JQuery知识快览之四—样式
- Linux设置禁止用户登陆
- 【JAVA - SSM】之SSM入门项目的搭建
- php基础知识【函数】(9)数学和对象类函数
- SELECT--UNION,UNION ALL,MINUS, INTERSECT,EXISTS
- werfault进程使用CPU率高
- matlab 写文件
- ELK对Tomcat日志双管齐下-告警触发/Kibana日志展示
- inno安装客户端,写注册表url调用客户端
- Nginx 安装配置
- 开源性能测试工具Locust使用篇(二)
- win10 图标异常 ,重命名后,图标不显示,名字错乱。
- pandas 常用清洗数据(三)排序,去重
- [shiro学习笔记]第四节 使用源码生成Shiro的CHM格式的API文档
- LeetCode152:Maximum Product Subarray
热门文章
- Python替换字符串中的反斜杠\
- 转:Conjugate prior-共轭先验的解释
- BZOJ4868:[SHOI2017]期末考试——题解
- BZOJ1458 士兵占领 【带上下界网络流】
- 洛谷 P4592 [TJOI2018]异或 解题报告
- HDOJ(HDU).2044-2049 递推专题
- 命令:ln 使用方法
- AtCoder Regular Contest 081 E - Don&#39;t Be a Subsequence(字符串DP)
- POI 10.28
- jdbcType和javaType