HDU-6119
2024-09-01 18:41:35
度度熊喜欢着喵哈哈村的大明星——星星小姐。
为什么度度熊会喜欢星星小姐呢?
首先星星小姐笑起来非常动人,其次星星小姐唱歌也非常好听。
但这都不是最重要的,最重要的是,星星小姐拍的一手好代码!
于是度度熊关注了星星小姐的贴吧。
一开始度度熊决定每天都在星星小姐的贴吧里面签到。
但是度度熊是一个非常健忘的孩子,总有那么几天,度度熊忘记签到,于是就断掉了他的连续签到。
不过度度熊并不是非常悲伤,因为他有m张补签卡,每一张补签卡可以使得某一忘签到的天,变成签到的状态。
那么问题来了,在使用最多m张补签卡的情况下,度度熊最多连续签到多少天呢?
Input本题包含若干组测试数据。
第一行两个整数n,m,表示有n个区间,这n个区间内的天数,度度熊都签到了;m表示m张补签卡。
接下来n行,每行两个整数(l[i],r[i]),表示度度熊从第l[i]天到第r[i]天,都进行了签到操作。
数据范围:
1<=n<=100000
0<=m<=1000000000
0<=l[i]<=r[i]<=1000000000
注意,区间可能存在交叉的情况。Output输出度度熊最多连续签到多少天。
Sample Input
2 1
1 1
3 3
1 2
1 1
Sample Output
3
3
Hint
样例一:度度熊补签第2天,然后第1天、第二天和第三天都进行了签到操作。
样例二:度度熊补签第2天和第3天。
题解:这里是贪心;我们可以先合并重合区间,然后排序,逐个遍历;看代码就明白了,很简单的
AC代码为:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; const int maxn = 1e5 + ;
int sum[maxn]; struct node {
int left;
int right;
node() {}
node(int li, int ri)
{
left = li;
right = ri;
}
}p[maxn]; bool cmp(node a, node b)
{
if (a.left == b.left)
return a.right < b.right;
return a.left < b.left;
} int main()
{
int n, m;
while (~scanf("%d%d", &n, &m))
{
memset(sum, , sizeof(sum)); for (int i = ; i <= n; i++)
{
cin >> p[i].left >> p[i].right;
} sort(p + , p + n + , cmp); int cnt = , Max;
for (int i = ; i <= n; i++)
{
int l = i, j = i + , Max = p[i].right;
while (p[j].left <= Max && j <= n)
{
Max = max(Max, p[j].right);
j++;
}
i = j - ;
p[cnt++] = node(p[l].left, Max); } for (int i = ; i<cnt; i++)
{
sum[i] = sum[i - ] + p[i].left - p[i - ].right - ;
} int max_total = m;
for (int l = , r = ; l<cnt; l++)
{
while (sum[r] - sum[l] <= m && r<cnt)
{
r++;
} max_total = max(max_total, p[r - ].right - p[l].left + + m + sum[l] - sum[r - ]);
} cout << max_total << endl;
} return ;
}
最新文章
- hdu 1872(看病要排队)(优先队列)
- spring注入静态成员变量提示invalid setter method
- Android 二维码扫描框 加四个角及中间横线自动下滑
- Linux下tomcat使用
- 通信协议:HTTP、TCP、UDP(转)
- 【Egret】里使用audio标签达到默认播放背景音乐
- js中数学运算的处理
- 【Android 系统开发】 编译 Android文件系统 u-boot 内核 并烧写到 OK-6410A 开发板上
- Learning ROS for Robotics Programming Second Edition学习笔记(六) indigo xtion pro live
- css3 绘制图形
- php闭包的使用实例
- 理解Hadoop脚本hadoop-2.5.0/bin/hadoop
- frameset,iframe框架之间如何互相调用变量、函数
- JavaScript之DOM概念
- Spring导出可以运行的jar包
- Andorid 翻书效果
- 20155237 2016-2017-2 《Java程序设计》第6周学习总结
- IOS和安卓WEB页面,input输入框被软键盘遮挡解决方法
- [Python爬虫]煎蛋网OOXX妹子图爬虫(1)——解密图片地址
- C# this关键字(给底层类库扩展成员方法)
热门文章
- java 实现一个死锁
- PHP经典面试题:如何保证缓存与数据库的双写一致性?
- Jquery 处理返回的 Json 数组
- Easy 2048 Again(状压dp)
- centos 更换用户密码
- 【论文阅读】Clustering Convolutional Kernels to Compress Deep Neural Networks
- html background-image 图片打开失败的原因
- 如何理解Nginx, WSGI, Flask(Django)之间的关系
- python与redis交互及redis基本使用
- MySQL双主+keepalived实现高可用实现(热备)