表决单调性

作者: 编程技术  发布:2019-09-20

题意

题目链接

4653: [Noi2016]区间

Time Limit: 60 Sec  Memory Limit: 256 MB
Submit: 621  Solved: 329
[Submit][Status][Discuss]

Sol

这题就是一个很显然的贪心。。。

首先二分一个答案,然后check是否可行。check的时候我们需要对每个位置,维护出所有左端点在左侧,右端点在右侧的所有区间。最优策略一定是加右端点最远的。

然后就做完了, 复杂度\)

#include<bits/stdc++.h>#define Fin freopen(#x".in", "r", stdin);#define LL long long #define int long long using namespace std;const int MAXN = 1e5 + 10;const LL INF = 1e18;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, M, K, A;vector<int> v[MAXN];LL a[MAXN], b[MAXN];bool check {    memset(b, 0, sizeof;    priority_queue<int> q;    int tag = 0, num = 0;    for(int i = 1; i <= N; i++) {        for(auto &x : v[i]) q.push;        while(!q.empty() && q.top q.pop();        tag += b[i];        int now = a[i] + tag;        while(now < mid && !q.empty() && q.top() >= i) {            b[q.top() + 1] -= A; tag += A; q.pop();            now += A; num++;        }        if(now < mid || num > K) return 0;    }    if(num <= K) return 1;}void solve() {    N = read(); M = read(); K = read(); A = read();    for(int i = 1; i <= N; i++) a[i] = read(), v[i].clear();    while {        int l = read(), r = read();        v[l].push_back;    }    int l = 0, r = INF, ans = -1;    while(l <= r) {        int mid = l + r >> 1;        if(check l = mid + 1, ans = mid;        else r = mid - 1;    }    cout << ans << 'n';}signed main() {    for(int T = read(); T--; solve;    return 0;}/**/

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 为该区间的左右端点。

N<=500000,M<=200000,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

HINT

 

Source

   style="font-size: 14pt;">首先我们考虑暴力怎么做,按长度排序之后,我们容易发现,如果枚举一个区间作为左端点,一个区间作为右端点,那么我们就是求只在这个区间中选取的答案。

style="font-size: 14pt;">  我们把这一段的所有区间的对应的一段的经过次数都加一,最后只需check一下这一段中是否出现了一个被经过m次的点,一旦存在就说明,我们一定可以找到其中的mm个区间满足题目的要求,所以我们就可以确保在这个区间中能够选取m个区间并一定合法,就可以用右端点的那个区间长度-左端点的那个区间长度来更新答案。(并不关心具体选了哪些区间)

style="font-size: 14pt;">  上述做法的复杂度可以用线段树维护来做到n2logn。深入思考可以发现,其实右端点肯定是不降的,所以我们没必要再枚举一个右端点,只要用单调指针一直往后扫即可。总复杂度为:O(nlogn)。

  (引自 ljh2000

#include<cstdio>
#include<algorithm>
#include<cstring>
#define lch k<<1
#define rch k<<1|1
using namespace std;
const int N=1e6+5,M=N<<2;
const int inf=2e9;
int n,m,p,cnt,ans=inf;
int mx[M],tag[M];
struct node{int l,r,len;}a[N>>1];int b[N];
inline bool cmp(const node &x,const node &y){
    return x.len<y.len;
}
inline void opera(int k,int v){
    mx[k]+=v;
}
inline void pushdown(int k,int l,int r){
    if(!tag[k]) return ;
    tag[lch]+=tag[k];opera(lch,tag[k]);
    tag[rch]+=tag[k];opera(rch,tag[k]);
    tag[k]=0;
}
void change(int k,int l,int r,int x,int y,int v){
    if(l==x&&r==y){
        opera(k,v);
        tag[k]+=v;
        return ;
    }
    pushdown(k,l,r);
    int mid=(l+r)>>1;
    if(y<=mid) change(lch,l,mid,x,y,v);
    else if(x>mid) change(rch,mid+1,r,x,y,v);
    else change(lch,l,mid,x,mid,v),change(rch,mid+1,r,mid+1,y,v);
    mx[k]=max(mx[lch],mx[rch]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),a[i].len=a[i].r-a[i].l;;
    for(int i=1;i<=n;i++) b[++cnt]=a[i].l,b[++cnt]=a[i].r;
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+cnt+1);cnt=unique(b+1,b+cnt+1)-(b+1);
    for(int i=1;i<=n;i++){
        a[i].l=lower_bound(b+1,b+cnt+1,a[i].l)-b,
        a[i].r=lower_bound(b+1,b+cnt+1,a[i].r)-b;
    }
    int top=1;
    for(int i=1;i<=n;i++){
        for(;mx[1]<m&&top<=n;top++){
            change(1,1,cnt,a[top].l,a[top].r,1);
        }
        if(mx[1]==m) ans=min(ans,a[top-1].len-a[i].len);
        change(1,1,cnt,a[i].l,a[i].r,-1);
    }
    printf("%dn",ans!=inf?ans:-1);
    return 0;
}

 

本文由贝博体育app发布于编程技术,转载请注明出处:表决单调性

关键词:

上一篇:没有了
下一篇:没有了