隐藏
「广州集训 Day2」瓜分领土 - 分类讨论+线段树 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「广州集训 Day2」瓜分领土 - 分类讨论+线段树

题目大意

石头、剪刀和布闹别扭了,他们要分家。
他们生活在一个离散的一维空间里,简单点说,他们拥有在一条直线上的N间房子,每间房子有一个风水值(有正有负)。
然后,他们决定将这$N$间房子分成非空的三个连续段,从左到右数,第一段的房子全部属于石头,第二段的房子全部属于剪刀,第三段的房子全部属于布。
由于他们希望公平,并且又由于剪刀是他们的老大哥,他们决定根据这些条件制定了一个评判标准:
设石头拥有的房子的风水值和为$a$,剪刀拥有的房子的风水值和为$b$,布拥有的房子的风水值和为$c$,剪刀拥有$n$间房子。
那么通过给定一个参数$x$。
那么,这种分配的合理值就是$max(a,b,c)-min(a,b,c)+x\times n$.
合理值越小,表示这种分配越合理。
因此,我们现在就是要求出这个最小的合理值。


题目分析

为了方便叙述,规定以下字母:
$a,b,c$与原题描述相同。
$x,y$分别表示三者的分界线,如图:

原题中的$x$使用$X$代替。
$sum[]$表示风水值前缀和。

这道题贼厉害的,若风水值全是非负数,那么可以枚举第一个分界点,然后三分查找第二个分界点即可。
然而风水值可能有负,因此前缀和不一定单调,就有问题了。

不妨讨论$6$种情况,将$max(a,b,c)-min(a,b,c)+x\times n$拆开。

在本处只讨论$a\ge b\ge c$这一种情况,其余5种情况请自行推(bao)导(zha)(本人推了1张/2页草稿纸)

当$a\ge b\ge c$时,用前缀和表示即为:

拆开化简得到:

不难发现,$y$合法的位置在$sum$的值域中是一段连续的区间。
因此我们可以对$sum$进行排序,二分出这段连续的区间的断点。

这样我们就可以确定$y$的合法区间,如何统计答案呢。
此时的合理值为:

化简得到:

我们可以枚举$x$,在线段树中查询$sum[y]+Xy$的最小值。

合并刚刚的限制条件与统计答案的信息,不难发现当$a\ge b\ge c$时,我们可以以$sum[y]$为下标,以$sum[y]+Xy$为值建立线段树。

具体的方案是,从大到小枚举$x$,将$y=x+1$的信息插入线段树,然后二分找到区间,在线段树中找到区间最小值。


细节

在上述推导二分区间时,出现了下面的式子:

因为普通的除以$2$会向下取整,因此可能将区间拓宽。
所以对于下界带除法的应向上取整。


代码

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
struct Tree {
int left,right;
LL min;
Tree(int l=0,int r=0,LL m=LLONG_MAX/2):left(l),right(r),min(m) {}
};
struct Segment_Tree {
Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index]=Tree(Left,Right);
if(Left==Right)return;
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
}
void push_up(int index) {
tree[index].min=min(tree[ls].min,tree[rs].min);
}
void modify(int index,int target,LL v) {
if(target>tree[index].right||target<tree[index].left)return;
if(tree[index].left==tree[index].right) {
tree[index].min=min(tree[index].min,v);
return;
}
modify(ls,target,v);
modify(rs,target,v);
push_up(index);
}
LL query(int index,int Left,int Right) {
if(Left>tree[index].right||Right<tree[index].left)return LLONG_MAX/2;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].min;
return min(query(ls,Left,Right),query(rs,Left,Right));
}
} st[7];
int n;
LL x,sum[maxn],sum2[maxn],ans=LLONG_MAX;
pair<LL,LL> bound(int pos,int id) {
LL up,down;
if(id==1) {
down=ceil((sum[n]+sum[pos])/2.0);
up=2*sum[pos];
}
if(id==2) {
down=sum[n]-sum[pos];
up=(sum[n]+sum[pos])/2.0;
}
if(id==3) {
down=ceil((sum[n]+sum[pos])/2.0);
up=sum[n]-sum[pos];
}
if(id==4) {
down=max(2*sum[pos],sum[n]-sum[pos]);
up=1e17;
}
if(id==5) {
down=-1e17;
up=min(2*sum[pos],sum[n]-sum[pos]);
}
if(id==6) {
down=2*sum[pos];
up=(sum[n]+sum[pos])/2.0;
}
return make_pair(down,up);
}
LL segment_val(int pos,int id) {
if(id==1)return sum[pos]+x*pos; //abc
if(id==2)return x*pos-sum[pos]; //acb
if(id==3)return sum[pos]+x*pos; //bca
if(id==4)return 2*sum[pos]+x*pos; //bac
if(id==5)return x*pos-2*sum[pos]; //cab
if(id==6)return x*pos-sum[pos]; //cba
}
LL get_ans(int pos,int id) {
if(id==1)return sum[pos]-sum[n]-x*pos;
if(id==2)return 2*sum[pos]-x*pos;
if(id==3)return -2*sum[pos]-x*pos;
if(id==4)return -sum[pos]-x*pos-sum[n];
if(id==5)return sum[n]+sum[pos]-x*pos;
if(id==6)return sum[n]-sum[pos]-x*pos;
}
void Solve(int pos,int id) {
pair<LL,LL> tmp=bound(pos,id);
LL down=tmp.first,up=tmp.second;
int l=lower_bound(sum2+1,sum2+n+1,down)-sum2,r=upper_bound(sum2+1,sum2+n+1,up)-sum2-1;
if(l>r)return;
ans=min(ans,get_ans(pos,id)+st[id].query(1,l,r));
}
struct number {
LL s;
int id;
bool operator < (const number& b) const {
return s<b.s;
}
} a[maxn];
int M[maxn];
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
sum[i]=a[i].s=a[i-1].s+Get_Int();
a[i].id=i;
}
x=Get_Int();
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)M[a[i].id]=i,sum2[i]=a[i].s;
for(int i=1; i<=6; i++)st[i].build(1,1,n);
for(int i=n-2; i>=1; i--)
for(int j=1; j<=6; j++) {
st[j].modify(1,M[i+1],segment_val(i+1,j));
Solve(i,j);
}
printf("%lld\n",ans);
return 0;
}
姥爷们赏瓶冰阔落吧~