codeforces-Ed92-D

codeforces-Ed92-D

七月 30, 2020

D. Segment Intersections

题意

有两种区间段[al,ar],[bl,br]

每个区间段有n个区间分别为

[al1,ar1],[al2,ar2]…[aln,arn]以及[bl1,br1],[bl2,br2]….[bln,brn]

要求最少扩张(区间向左或向右扩张1个单位)几次

使得$∑ intersection length([ali,ari],[bli,bri]) =k $

注意只考虑下标相同的[ali,ari]和[bli,bri]重叠区间长度 而[alx,arx]与[bly,bry] (x!=y) 不计算重叠长度

题解

分类讨论

若两个区间有交集

那么仅仅扩张一个单位区间a或区间b 就能使重叠区间+n (1换1)

若a和b的区间被扩张到完全重合仍然不能满足$∑ intersection length([ali,ari],[bli,bri]) =k $

那么两个区间同时扩张 一个单元 使得重叠区间+n (2 换1)

再讨论没有交集的情况

根据样例发现 可以从n对区间中选择一部分x对区间进行扩张

计算达到k个重叠单位长度所需要的操作次数

然后暴力枚举x 更新最小操作次数

每次枚举到对x对区间操作时 以同样的策略扩张 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
int data[Max];
/*
*/
int main() {
    Turnoff;
    int t;cin>>t;
    while(t--){
        ll n,k;cin>>n>>k;
        ll al,ar,bl,br;
        cin>>al>>ar>>bl>>br;
        ///让a区间整体小于b区间
        if(al>bl){
            swap(al,bl);
            swap(ar,br);
        }
        ///分情况有交集
        if(bl<=ar){
            ll inlen=min(ar,br)-bl;
            ll extend=max(ar,br)-min(al,bl)-inlen;
            k-=inlen*n;///减去已经重叠的部分
            if(k<=0)cout<<0<<endl;
            else if(extend*n>=k)cout<<k<<endl;
            ///若扩张到ab区间重合时重叠面积超过k
            ///那么显然可以只用k次就达到要求
            else cout<<extend*n+(k-extend*n)*2<<endl;
            ///若扩张到等长度仍然不够用那么让两个区间同时扩张
            ///只用其中a中(k-extend*n)个区间和b中(k-extend*n)个区间同时扩张
        }
        else{///没有交集
            ll step=1e18;
            for(ll i=1;i<=n;i++){
                ll temp=i*(bl-ar);
                ll extend=br-al;
                if(extend*i>=k)step=min(step,temp+k);
                else step=min(step,temp+extend*i+(k-extend*i)*2ll);
            }
            cout<<step<<endl;
        }
    }
}