題干：

度度熊喜歡著喵哈哈村的大明星——星星小姐。?

為什么度度熊會喜歡星星小姐呢？?

首先星星小姐笑起來非常動人，其次星星小姐唱歌也非常好聽。?

但這都不是最重要的，最重要的是，星星小姐拍的一手好代碼！?

于是度度熊關注了星星小姐的貼吧。?

一開始度度熊決定每天都在星星小姐的貼吧里面簽到。?

但是度度熊是一個非常健忘的孩子，總有那么幾天，度度熊忘記簽到，于是就斷掉了他的連續簽到。?

不過度度熊并不是非常悲傷，因為他有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天。

? ? ? ??
解題報告：

? ?注意幾個細節，這里最好 讓r=2，以免會上來就減掉一部分m。第二就是首先要對ans進行初始化，因為剛進入while循環的時候是不會進行更新ans的，，，這里相當于忽略了一個可能的答案。還有就是更新ans的時候，不需要記錄m具體放在什么位置，因為你區間的選擇都是符合條件的，剩下的m都添加在后面就可以了，當然添加在前面也是可以的，，但是這種情況應該在之前就已經更新過了。。。總之最終一定會得到最優解。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; struct R{int l,r; } a[MAX],b[MAX]; bool cmp(R a,R b) {if(a.l!=b.l) return a.l<b.l;else return a.r>b.r; } int main() {int n,m;while(~scanf("%d%d",&n,&m)) {for(int i = 1; i<=n; i++) scanf("%d%d",&a[i].l,&a[i].r);sort(a+1,a+n+1,cmp);int tot=1;b[1]=a[1];for(int i = 2; i<=n; i++) {if(a[i].l<=b[tot].r+1) b[tot].r = max(b[tot].r,a[i].r);else b[++tot] = a[i];}int l = 1,r = 2,ans = b[1].r-b[1].l+m+1;//注意初始化 否則需要 while(r<=tot) { // ans = max(ans,b[r-1].r-b[l].l+1+m);//加這一句 m -= b[r].l - b[r-1].r-1;while(m<0&&l<=r) {m+=b[l+1].l-b[l].r-1;l++;}ans = max(ans,b[r].r-b[l].l+1+m);r++;}if(m>0) ans = max(ans,b[tot].r-b[l].l+1+m);printf("%d\n",ans);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 6119】小小粉丝度度熊 （区间合并，尺取，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。