在线旅游网站开发分析报告,专业网站策划 西安,免费无代码开发软件推荐,网站免费云主机题目描述
在数轴上有 n 个闭区间从 1 至 n 编号#xff0c;第 i 个闭区间为 [li,ri] 。
现在要从中选出 m 个区间#xff0c;使得这 m 个区间共同包含至少一个位置。换句话说#xff0c;就是使得存在一个 x #xff0c;使得对于每一个被选中的区间 [li,ri]#…题目描述
在数轴上有 n 个闭区间从 1 至 n 编号第 i 个闭区间为 [li,ri] 。
现在要从中选出 m 个区间使得这 m 个区间共同包含至少一个位置。换句话说就是使得存在一个 x 使得对于每一个被选中的区间 [li,ri]都有 li≤x≤ri 。
对于一个合法的选取方案它的花费为被选中的最长区间长度减去被选中的最短区间长度。
区间[li,ri] 的长度定义为 (ri−li) 即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案输出 −1。
输入格式
第一行包含两个整数分别代表 n 和 m。
第 2 到第(n1) 行每行两个整数表示一个区间第 (i1) 行的整数 li,ri 分别代表第 i 个区间的左右端点。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1复制
6 3
3 5
1 2
3 4
2 2
1 5
1 4
输出 #1复制
2
说明/提示
样例1 解释 解析:
从题目中我们可以观察到选着线段和 顺序无关我们可以进行排序。
暴力做法就是
我们对线段的长度进行从小到大排序
当遍历到有点满足x m时 当前 j 减去 i ;
时间复杂度为On^2); 爆
我们对区间搜索进行我们可以用线段树记录区间的 x 进行优化离散化一下 防止无用的点
在利用区间 的 查询时我们要记录其区间 的中的个数。
在利用双指针进行搜索
i j 含义 i 代表当在i点如果 满足其 m个时我们i。 while(t[1].cnt m i j) { i; change(1,s[i].l,s[i].r,-1); } ans min(s[j].len - s[i].len,ans); 这里要注意 i 是当前满足条件的 点 下一个点 就不满足了。 因为我们是 线段长度从小到大 遍历。 所以i 和 j越靠近越小。 代码
#includebits/stdc.h
using namespace std;
#define ls u1
#define rs u1|1
const int N 500005;
struct line{int l,r,len;bool operator (line b){return len b.len;}
}s[N];
struct node{int l,r,cnt,lazy;
}t[N*2*4];
void pushup(int u)
{t[u].cnt max(t[ls].cnt ,t[rs].cnt);
}
void build(int u,int l,int r)
{t[u].l l,t[u].r r;t[u].cnt 0;if(l r){return;} int mid l r1;build(ls,l,mid);build(rs,mid1,r);pushup(u);
}
void downup(int u){if(t[u].lazy){t[ls].lazy t[u].lazy;t[rs].lazy t[u].lazy;t[ls].cnt t[u].lazy;t[rs].cnt t[u].lazy;t[u].lazy 0;}
}void change(int u,int l,int r,int v)
{if(t[u].l r || t[u].r l){return;}if(t[u].l l t[u].r r){t[u].lazy v;t[u].cnt v;return;}downup(u);change(ls,l,r,v);change(rs,l,r,v);pushup(u);//这个没有加
}int main()
{int n,m;cin n m;vectorint v(n*2);int j 0;for(int i 1;i n;i){cin s[i].l s[i].r;s[i].len s[i].r - s[i].l1;v[j] s[i].l;v[j] s[i].r;}sort(v.begin(),v.end());int k unique(v.begin(),v.end()) - v.begin();sort(s1,s1n);for(int i 1;i n;i){s[i].l lower_bound(v.begin(),v.begin()k,s[i].l) - v.begin();s[i].r lower_bound(v.begin(),v.begin()k,s[i].r) - v.begin();}build(1,1,k);int ans 1e9;for(int i 0,j 0;j n;){while(t[1].cnt m j n){j;change(1,s[j].l,s[j].r,1); }if(t[1].cnt m) break;while(t[1].cnt m i j){i;change(1,s[i].l,s[i].r,-1); } ans min(s[j].len - s[i].len,ans);}cout (ans 1e9 ? -1 : ans);return 0;
}
时间复杂度On*logn
