Wuyanru's blog
0%

[CEOI2022] Measures

发表于 分类于 ，

模拟赛题。

感觉考场上随便推一下应该就会做了，但是我就是坐那干瞪了一整场。

那应该还是我菜了

题目链接

题意

现在有一根数轴，这个数轴上初始有 个人，其中第 个人的坐标为 。

每一个人都可以以每秒 单位长度的速度进行移动。

你需要求出，最优情况下，需要多少时间让他们来回走动，使得两两距离都 ，其中 为输入给定的数字。

特别地，本题有 次插入操作，第 次操作插入一个在 的人，你需要在每一次插入操作后，输出上述问题的答案。

题解

感觉是一个小结论题，但是结论稍微推一下就能推出来。

假设只有单组询问，我们首先将所有人按照初始位置排序，他们的最终顺序显然和初始顺序一样，

即不可能有两人相对方向交换。

设第 个人初始位置为 ，最终位置是 ，时间（即答案）为 。

首先显然，对于任意两个人 ，会有 。

比较显然，因为这两个人中间恰有 个间隔，每一个间隔长度都至少是 。

把上面的式子稍化一下，就可以得到 。

其次，我们还有每一个人最终位置的限制，即 。

我们发现上面一条，两个人在比较时，采用的是 ，所以我们把下面的限制也改一下。

其实整个问题其实在问，选择一个最小的 ，使得每一个人 能选择一个数字 ，使得 且 。

假如我们已经确定了 是多少，能否知道这个 是否合法呢？

因为有了 递增这个限制，我们肯定是让前面的 越小越好。

所以从贪心的角度考虑，我们选择的 一定有 。

我们只需要检查一下是否有所有 就好了。

不难发现，上述检验是充要的。

然后呢？

再仔细观察，我们会发现有一个更简单的式子：

很好证明，对上面 的式子进行归纳即可。

而 合法的充要条件，其实就是对于任意的 ，有 。

所以，

我们要求的最小的 其实就是

线段树进行统计即可。

时间复杂度 。

代码

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
using ll=long long;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
struct node
{
    int id;
    int x;
}a[400001];
ll num[1600001];
ll ma[1600001];
ll mi[1600001];
ll c[1600001];
int t[400001];
int w[400001];
int x[400001];
int n,m,d;
int cnt;
void build(int p,int pl,int pr)
{
    num[p]=-inf,ma[p]=-inf,mi[p]=inf;
    if(pl==pr) return ;
    int mid=(pl+pr)>>1;
    build(p*2,pl,mid);
    build(p*2|1,mid+1,pr);
}
inline void push_up(int p)
{
    c[p]=c[p*2]+c[p*2|1];
    ma[p]=max(ma[p*2],ma[p*2|1]-d*c[p*2]);
    mi[p]=min(mi[p*2],mi[p*2|1]-d*c[p*2]);
    num[p]=max(max(num[p*2],num[p*2|1]),ma[p*2]-(mi[p*2|1]-c[p*2]*d));
}
void change(int p,int pl,int pr,int x,int y)
{
    if(pl==pr)
    {
        mi[p]=ma[p]=y;
        c[p]=1,num[p]=0;
        return ;
    }
    int mid=(pl+pr)>>1;
    if(x<=mid) change(p*2,pl,mid,x,y);
    else change(p*2|1,mid+1,pr,x,y);
    push_up(p);
}
inline void solve()
{
    build(1,1,n+m);
    for(int i=1;i<=n+m;i++)
    {
        change(1,1,n+m,w[i],x[i]);

        if(i>n)
        {
            ll ans=max(num[1],0ll);
            if(num[1]&1) printf("%lld.5 ",ans/2);
            else printf("%lld ",ans/2);
        }
    }
}
int main()
{
    n=read(),m=read(),d=read();
    for(int i=1;i<=n+m;i++)
    {
        a[i].x=x[i]=read();
        a[i].id=i;
    }
    sort(a+1,a+n+m+1,[](node a,node b){ return a.x<b.x;});
    for(int i=1;i<=n+m;i++) w[a[i].id]=i;
    solve();
    return 0;
}

感谢观看！