宁乡电商网站建设收费,网站左下角广告代码,wordpress教程登陆,怎么在百度上发布信息【BZOJ4653】[Noi2016]区间 Description 在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间#xff0c;使得这 m个区间共同包含至少一个位置。换句话说#xff0c;就是使得存在一个 x#xff0c;使得对于每一个被选中的区间 [li,ri]#xff0c;都…【BZOJ4653】[Noi2016]区间 Description 在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间使得这 m个区间共同包含至少一个位置。换句话说就是使得存在一个 x使得对于每一个被选中的区间 [li,ri]都有 li≤x≤ri。 对于一个合法的选取方案它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li即等于它的右端点的值减去左端点的值。 求所有合法方案中最小的花费。如果不存在合法的方案输出 −1。 Input 第一行包含两个正整数 n,m用空格隔开意义如上文所述。保证 1≤m≤n 接下来 n行每行表示一个区间包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。 N500000,M200000,0≤li≤ri≤10^9 Output 只有一行包含一个正整数即最小花费。 Sample Input 6 3 3 5 1 2 3 4 2 2 1 5 1 4 Sample Output 2 题解这不是我最喜爱的没有之一双指针法吗然而GXZ没等我看题就告诉我正解简直丧心病狂~ 因为总代价只和最长区间和最短区间有关我们将区间按长度排序那么中间的区间都可以免费取。我们采用双指针法枚举右端点r再不断右移l直到[l,r]中的区间刚好满足条件。是否满足条件可以用线段树判定只需要再每次平移指针的时候维护一下线段树就行了。 #include cstdio
#include iostream
#include cstring
#include algorithm
#define lson x1
#define rson x1|1
using namespace std;
const int maxn500010;
int n,m,nm,ans;
int s[maxn4],t[maxn4];
struct node
{int len,a,b;
}p[maxn];
struct number
{int val,org,k;
}num[maxn1];
bool cmp1(node a,node b)
{return a.lenb.len;
}
bool cmp2(number a,number b)
{return a.valb.val;
}
int rd()
{int ret0,f1; char gcgetchar();while(gc0||gc9) {if(gc-)f-f; gcgetchar();}while(gc0gc9) retret*10gc-0,gcgetchar();return ret*f;
}
void updata(int l,int r,int x,int a,int b,int v)
{if(alrb){s[x]v,t[x]v;return ;}if(t[x]) s[lson]t[x],s[rson]t[x],t[lson]t[x],t[rson]t[x],t[x]0;int midlr1;if(amid) updata(l,mid,lson,a,b,v);if(bmid) updata(mid1,r,rson,a,b,v);s[x]max(s[lson],s[rson]);
}
int main()
{nrd(),mrd();int i,j;for(i1;in;i)num[i].valrd(),num[in].valrd(),num[i].orgnum[in].orgi,num[in].k1,p[i].lennum[in].val-num[i].val;sort(num1,num2*n1,cmp2);num[i-1].val-1;for(i1;i2*n;i){if(num[i].valnum[i-1].val) nm;if(num[i].k) p[num[i].org].bnm;else p[num[i].org].anm;}sort(p1,pn1,cmp1);ans130;for(i1;ins[1]m;updata(1,nm,1,p[i].a,p[i].b,1),i);if(ins[1]m){printf(-1);return 0;}i--,updata(1,nm,1,p[i].a,p[i].b,-1);for(j1;in;i){for(updata(1,nm,1,p[i].a,p[i].b,1);jis[1]m;updata(1,nm,1,p[j].a,p[j].b,-1),j);j--,updata(1,nm,1,p[j].a,p[j].b,1);ansmin(ans,p[i].len-p[j].len);}printf(%d,ans);return 0;
}
//6 3 3 5 1 2 3 4 2 2 1 5 1 4 转载于:https://www.cnblogs.com/CQzhangyu/p/7130202.html
