Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


百度之星初赛B--小小粉丝度度熊

传送门

题目描述

度度熊喜欢着喵哈哈村的大明星——星星小姐。

为什么度度熊会喜欢星星小姐呢?

首先星星小姐笑起来非常动人,其次星星小姐唱歌也非常好听。

但这都不是最重要的,最重要的是,星星小姐拍的一手好代码!

于是度度熊关注了星星小姐的贴吧。

一开始度度熊决定每天都在星星小姐的贴吧里面签到。

但是度度熊是一个非常健忘的孩子,总有那么几天,度度熊忘记签到,于是就断掉了他的连续签到。

不过度度熊并不是非常悲伤,因为他有m张补签卡,每一张补签卡可以使得某一忘签到的天,变成签到的状态。

那么问题来了,在使用最多m张补签卡的情况下,度度熊最多连续签到多少天呢?


输入描述

本题包含若干组测试数据。

第一行两个整数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

注意,区间可能存在交叉的情况。


输出描述

输出度度熊最多连续签到多少天。


解题思路

先预处理所给数据,得到不交叉的len个区间,尺取法找到最大区间。
拓展一下——尺取法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>  
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
int l, r;
}a[100005];
bool cmp(const node & a,const node & b){
if(a.l == b.l) return a.r < b.r;
return a.l < b.l;
}
int hole[100005];
int main(){
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%d%d", &a[i].l, &a[i].r);
}
sort(a, a + n,cmp);
int cnt = 0;
for (int i = 1; i < n; i++) {
if (a[i].r <= a[cnt].r) continue;
if (a[i].l <= a[cnt].r + 1) {
a[cnt].r = a[i].r;
continue;
}
cnt++;
a[cnt] = a[i];
}
for (int i = 0; i < cnt;i++) {
hole[i] = a[i + 1].l - a[i].r - 1;
}
int nl = 0,nr = 0;
int re = m,te = m;
while (nr <= cnt) {
while (nr < cnt && te >= hole[nr]) {
te -= hole[nr];
nr++;
}
re = max(re, a[nr].r - a[nl].l + 1 + te);
if (nl != nr) {
te += hole[nl];
}
nl++;
if (nl > nr) nr++;
}
printf("%d\n", re);
}
return 0;
}

Markdown

最近的文章

[UOJ Round #8]赴京赶考

传送门题目描述 高中,高中,短暂的三年。NOI是高中结业考试,而高考在每年暑假举行。 高二暑假,这是你最后一次参加高考的机会。你已经为了高考停课很久了,OI的知识很久没管了。你并没有能力用一年时间补起别人三年的OI课程。这是你的最后一战,如果你失败了,可能就不能工地搬砖只能去清华了。 这天你背上行囊 …

于  贪心 继续阅读
更早的文章

矩阵快速幂

于 继续阅读