admin管理员组文章数量:1573363
solution:
不看题解做不出来
考虑翻转一些区间使得答案更优。(这里不讨论
[
l
,
r
]
=
∅
[l,r] = \empty
[l,r]=∅ 的情况)
设
a
i
a_i
ai 表示翻转前的答案,
b
i
b_i
bi 表示翻转后的答案。
性质一:任意两个翻转的区间一定有交集。
证明:考虑反证。假设有两个翻转区间交集为空,那么翻转前肯定比翻转后更优。
性质二:设所有翻转区间交集为
[
l
,
r
]
[l,r]
[l,r] ,其中
b
t
=
max
(
a
l
,
.
.
,
a
r
)
b_t=\max(a_l,..,a_r)
bt=max(al,..,ar) ,
l
≤
t
≤
r
l\le t\le r
l≤t≤r 。则满足
b
t
≥
max
(
b
i
)
−
1
b_t\ge \max(b_i)-1
bt≥max(bi)−1 。
证明:当
l
≤
t
′
≤
r
l\le t'\le r
l≤t′≤r 时显然成立 。否则任意撤销一个翻转区间,答案不会更劣。
性质三:
t
t
t 满足
a
t
=
max
(
a
i
)
a_t=\max(a_i)
at=max(ai)
证明:当
l
≤
t
′
≤
r
l\le t'\le r
l≤t′≤r 时显然成立。考虑反证,假设
a
t
<
a
t
′
a_t<a_t'
at<at′ ,用
a
t
−
b
t
a_t-b_t
at−bt 表示经过 t 的翻转区间的个数, 则有
a
t
−
b
t
≥
a
t
′
−
b
t
′
+
1
a_t-b_t\ge a_t'-b_t'+1
at−bt≥at′−bt′+1 (否则
t
′
t'
t′ 也是公共点),即
a
t
+
b
t
′
≥
b
t
+
a
t
′
+
1
a_t+b_t'\ge b_t+a_t'+1
at+bt′≥bt+at′+1 ,这与性质二和假设矛盾。
性质四:对于任意满足
a
t
=
m
a
x
(
a
i
)
a_t=max(a_i)
at=max(ai) 的点 ,一定满足
t
∈
[
l
,
r
]
t\in [l,r]
t∈[l,r]
证明:和性质三类似。
现在我们考虑算法流程:
首先二分答案 w w w ,为了便于确定一个点的最终状态,我们还需要得到翻转区间的个数 c n t = a [ t ] − w cnt=a[t]-w cnt=a[t]−w 或 c n t = a [ t ] − w + 1 cnt=a[t]-w+1 cnt=a[t]−w+1 。
贪心算法流程如下:
- 求出最左边的满足 a t = max ( a i ) a_t=\max(a_i) at=max(ai) 的点,作为我们的 t t t ( t ∈ [ l , r ] ) (t\in [l,r]) (t∈[l,r])
- 从左往右扫描线,将左端点对应的塞进 r r r 的优先队列
- 设 p p p 表示当前已经选择的翻转区间的个数,判断 a [ i ] − p + c n t − p > w a[i]-p+cnt-p > w a[i]−p+cnt−p>w 是否满足;
- 最后可以证明 p = c n t p=cnt p=cnt 。再扫描一遍 [ t + 1 , n ] [t+1,n] [t+1,n] 是否超过 w w w ,可以差分数组维护
时间复杂度 O ( n log 2 n ) O(n\log^2n) O(nlog2n) 。
总结:思路并不复杂,但是结论很难想,也比较抽象。
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define All(a) a.begin(),a.end()
using namespace std;
const int Maxn=2e5+5;
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
int n,m;
ll a[Maxn],d[Maxn],cf[Maxn];
vector<int> vec[Maxn];
struct node{
int l,r,c;
}q[Maxn];
priority_queue<pair<int,int>> Q;
bool check(ll w,int t,ll cnt) {
for(int i=1;i<=n;i++) cf[i]=0,d[i]=a[i];
for(int i=1;i<=n;i++) {
vec[i].clear();
}
while(Q.size()) Q.pop();
for(int i=1;i<=m;i++) {
if(q[i].l<=t&&t<=q[i].r) {
vec[q[i].l].push_back(i);
}
}
ll p=0;
for(int i=1;i<=t;i++) {
for(auto y:vec[i]) {
Q.push(make_pair(q[y].r,q[y].c));
}
while(a[i]-p+cnt-p>w) {
if(!Q.size()) return 0;
int pr=Q.top().fi; ll c=Q.top().se; Q.pop();
ll ps=min(c,(a[i]-p+cnt-p-w+1)/2);
p+=ps;
cf[pr]+=2*ps;
if(ps!=c) Q.push(make_pair(pr,c-ps));
}
}
cf[t]-=cnt;
for(int i=t+1;i<=n;i++) {
cf[i]+=cf[i-1];
if(cf[i]+a[i]>w) return 0;
}
return 1;
}
signed main() {
n=read(),m=read();
for(int i=1;i<=m;i++) {
q[i].l=read(),q[i].r=read(),q[i].c=read();
if(q[i].l>q[i].r) swap(q[i].l,q[i].r);
a[q[i].l]+=q[i].c; a[q[i].r]-=q[i].c;
}
int tl,tr; ll tmax=0;
for(int i=1;i<=n;i++) {
a[i]+=a[i-1];
tmax=max(tmax,a[i]);
}
for(int i=1;i<=n;i++) {
if(a[i]==tmax) {
tr=i;
}
}
for(int i=n;i>=1;i--) {
if(a[i]==tmax){
tl=i;
}
}
ll l=1,r=a[tl],res=0;
while(l<=r) {
ll mid=l+r>>1;
if(check(mid,tl,a[tl]-mid)||check(mid,tl,a[tl]-mid+1)) res=mid,r=mid-1;
else l=mid+1;
}
printf("%lld",res);
}
版权声明:本文标题:【题解】「JOISC 2017 Day 2」门票安排 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1727745771a1127778.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论