首页 > 代码库 > [Noi2016]区间

[Noi2016]区间

2024-10-17 11:18:39   215人阅读

题目描述

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri?li，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 ?1。

输入输出格式

输入格式：

 

第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n

接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。

N<=500000,M<=200000,0≤li≤ri≤10^9

输出格式：

只有一行，包含一个正整数，即最小花费。

输入输出样例

输入样例#1：
6 3
3 5
1 2
3 4
2 2
1 5
1 4
输出样例#1：
2

说明

技术分享

技术分享

题解：

离散化+线段树维护+决策单调性

先将数据离散，但区间长不变。

按区间长从小到大排序，可知单调性：当最大值大于m时，再增加区间不会使答案减小，即当前最优解(意思是不必在往后走，而不是全局最优)。

具体实现与单调队列一样，不过区间的和用线段树维护，当小于m时入队

将当前答案与ans比较记下，队首出队，继续执行。

注意队尾要小于等于n，与ans比较时，区间和必须大于m

 

 1 #include<iostream>  
 2 #include<cstring>  
 3 #include<cstdio> 
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;  
 7 struct Messi
 8 {
 9     int x,y,l;
10 }a[10000111];
11 int k,p[10000111],lazy[10000110],c[10000111],n,m,ans;
12 bool vis[10000111];
13 int find(int x)
14 {int l,r;
15     l=1;r=k;
16     while (l<r)
17     {
18         int mid=(l+r)/2;
19         if (p[mid]>=x) r=mid;
20         else l=mid+1;
21     }
22     return l;
23 }
24 bool cmp(Messi a,Messi b)
25 {
26     return (a.l<b.l);
27 }
28 void pushdown(int rt)
29 {
30     if (lazy[rt]!=0)
31     {
32         lazy[rt*2]+=lazy[rt];
33         lazy[rt*2+1]+=lazy[rt];
34         c[rt*2]+=lazy[rt];
35         c[rt*2+1]+=lazy[rt];
36         lazy[rt]=0;
37     }
38 }
39 void update(int rt,int l,int r,int L,int R,int k)
40 {
41     if (l!=r) pushdown(rt);
42     if (l>=L&&r<=R)
43     {
44         c[rt]+=k;
45         lazy[rt]+=k;
46         return;
47     }
48     
49     int mid=(l+r)/2;
50      if (L<=mid) update(rt*2,l,mid,L,R,k);
51      if (R>mid) update(rt*2+1,mid+1,r,L,R,k);
52      c[rt]=max(c[rt*2],c[rt*2+1]);
53 }
54 int main()
55 {int i,j;
56     cin>>n>>m;
57     for (i=1;i<=n;i++)
58     {
59         scanf("%d%d",&a[i].x,&a[i].y);
60         {
61             k++;
62             p[k]=a[i].x;
63         }
64         {
65             k++;
66             p[k]=a[i].y;
67         }
68         a[i].l=a[i].y-a[i].x;
69     }
70      sort(p+1,p+k+1);
71      for (i=1;i<=n;i++)
72      {
73          a[i].x=find(a[i].x);
74          a[i].y=find(a[i].y);
75      }
76      sort(a+1,a+n+1,cmp);
77      j=0;
78      ans=2e9;
79      for (i=1;i<=n;i++)
80      {
81       if (j==n) break;
82          while (c[1]<m&&j<n)
83          {
84          j++;
85              update(1,1,k,a[j].x,a[j].y,1);    
86          }
87          if (c[1]>=m) ans=min(a[j].l-a[i].l,ans);
88          update(1,1,k,a[i].x,a[i].y,-1);
89      }
90      if (ans==2e9)
91      cout<<-1;
92      else 
93      cout<<ans;
94 }

 

[Noi2016]区间


联系
我们