hdu 6119 小小粉丝度度熊(区间双指针)

题目链接:hdu 6119 小小粉丝度度熊

题意:

给你n个区间,和一个数m,m表示可补上不连续的位置累计和为m,现在问你最长的连续区间和为多少。

题解:

我可能写的有点复杂,大概就是将每个区间排序后离散化,将这些间隔看成一个点,然后双指针一下。

 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 4 using namespace std;
 5 typedef pair<int,int>P;
 6 
 7 const int N=1e5+7;
 8 int n,m,hsh[N*3],ed,cnt[N*4],ced,C[N*4];
 9 int IS[N*4];
10 P seg[N];
11 
12 void add(int x,int v){while(x<=ced)C[x]+=v,x+=x&-x;}
13 int ask(int x){int an=0;while(x)an+=C[x],x-=x&-x;return an;}
14 
15 void solve()
16 {
17     int ans=0,cha=m,sum=0;
18     for(int l=1,r=1;r<=ced;r++)
19     {
20         int is=IS[r];
21         if(is)sum+=cnt[r];
22         else cha-=cnt[r],sum+=cnt[r];
23         while(l<=r&&cha<0)
24         {
25             int is=IS[l];
26             if(is)sum-=cnt[l];
27             else cha+=cnt[l],sum-=cnt[l];
28             l++;
29         }
30         ans=max(ans,sum+cha);
31     }
32     printf("%d
",ans);
33 }
34 
35 int main(){
36     while(~scanf("%d%d",&n,&m))
37     {
38         ced=0;mst(C,0);mst(IS,0);
39         ed=0;hsh[++ed]=0;hsh[++ed]=(int)(1e9+7);
40         F(i,1,n)
41         {
42             scanf("%d%d",&seg[i].first,&seg[i].second);
43             seg[i].first++,seg[i].second++;
44             hsh[++ed]=seg[i].first,hsh[++ed]=seg[i].second;
45         }
46         sort(hsh+1,hsh+1+ed),ed=unique(hsh+1,hsh+1+ed)-hsh-1;
47         F(i,2,ed)
48         {
49             cnt[++ced]=hsh[i]-hsh[i-1]-1;
50             cnt[++ced]=1;
51         }
52         F(i,1,n)
53         {
54             int idx=lower_bound(hsh+1,hsh+1+ed,seg[i].first)-hsh;
55             idx=(idx-1)*2;
56             add(idx,1);
57             idx=lower_bound(hsh+1,hsh+1+ed,seg[i].second)-hsh;
58             idx=(idx-1)*2;
59             add(idx+1,-1);
60         }
61         F(i,1,ced)IS[i]=ask(i);
62         solve();
63     }
64     return 0;
65 }
View Code
原文地址:https://www.cnblogs.com/bin-gege/p/7354287.html