当前位置: 首页 > news >正文

题解:P13507 [OOI 2024] Three Arrays

模拟赛搬的题,假了一万次,我也不知道咋搞过去的。

食用本题解时需要感性理解每个操作和定义的合理性,最好不要先去想这么搞的必要性。

我们可以对两个数分开考虑,由于两者顺序无影响。为方便这里将 \(L\)\(R\) 数组统一记作上界 \(x\)

定义一个取 \(\min\) 操作比另一个取 \(\min\) 操作强,当且仅当删去另一个操作后不会对最终答案产生影响。
分析可以发现,其充要条件是前者的上界加上两者之间的变化量(根据位置可能为负)小于等于后者的上界。
形式化的,就是当 \(x_i+pre_j-pre_i\le x_j\) 又记作 \(x_i-pre_i\le x_j-pre_j\) 时,我们认为 \(i\) 强于 \(j\)\(pre\) 数组为 \(D\) 数组的前缀和。
特别的,当\(x_i+pre_j-pre_i=x_j\) 时,我们仅在满足 \(i<j\) 时认为 \(i\) 强于 \(j\),方便排序。

同时,需要预先将 \(L\)\(R\) 数组里的每个值与可能最大值(无前缀操作情况)取 \(\min\),这样可以使得无操作为最弱操作。

那么贪心的想,对于一个操作序列,我们把不强于当前最强操作,且不在序列里的操作选过来一定是不劣的,因为这样不会使当前答案增加,同时还可能使另一个序列答案增大。

显然的,一个操作是最强的当且仅当比他强的都选了另一边,这一性质同时成立。

然后就会有一种做法是枚举一个序列的最强操作,将且仅将比它强的操作选到另一边,可以发现,这就是最强操作为当前操作时的答案最大值,然后将所有最强操作情况答案取 \(\max\) 就是最终答案。

具体维护的话我们可以将两个序列的操作分别从强到弱排序,然后对于其中一个序列的操作从前到后枚举最强操作(还有空操作情况),同时记录必须选到另一边的操作(就是前缀操作)中在另一边最强操作(初始为空操作),两者分别计算答案相加再取最大值即可。

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int x[N],L[N],R[N],y[N],numa[N],numb[N],ida[N],idb[N],n;
bool cmpa(int u,int v){if(L[u]-y[u]!=L[v]-y[v])return L[u]-y[u]<L[v]-y[v];return u<v;
}
bool cmpb(int u,int v){if(R[u]-y[u]!=R[v]-y[v])return R[u]-y[u]<R[v]-y[v];return u<v;
}
signed main(){scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&x[i]);for(int i=1;i<=n;i++)scanf("%lld",&L[i]);for(int i=1;i<=n;i++)scanf("%lld",&R[i]);scanf("%lld%lld",&L[0],&R[0]);for(int i=1;i<=n;i++)y[i]=y[i-1]+x[i];for(int i=1;i<=n;i++){L[i]=min(L[i],L[0]+y[i]);R[i]=min(R[i],R[0]+y[i]);}for(int i=1;i<=n;i++)numa[i]=numb[i]=i;sort(numa+1,numa+n+1,cmpa);sort(numb+1,numb+n+1,cmpb);for(int i=1;i<=n;i++){ida[numa[i]]=i;idb[numb[i]]=i;}int ans=0,now=n+1;for(int i=1;i<=n;i++){ans=max(ans,R[numb[now]]+y[n]-y[numb[now]]+y[n]-y[numa[i]]+L[numa[i]]);now=min(now,idb[numa[i]]);}ans=max(ans,R[numb[now]]+y[n]-y[numb[now]]+y[n]+L[0]);printf("%lld\n",ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=20105

相关文章:

  • 题解:AT_abc424_f [ABC424F] Adding Chords
  • 如何在不同区域/网络环境下评估 reCAPTCHA 的表现 - 详解
  • 2025 年最新编织袋生产厂家权威推荐排行榜:聚焦 TOP5 优质企业,助力企业精准甄选可靠合作伙伴牛皮纸/塑料/PP彩膜/化工/化肥编织袋厂家推荐
  • P11854 [CSP-J2022 山东] 宴会
  • 2025 年试验机厂家权威推荐榜:TOP5 优质厂家综合实力解析,助力科研与工业客户精准选型电子万能材料/橡胶拉力/塑料拉力/扬州拉力试验机厂家推荐
  • win 系统安装
  • 2025 年节能咨询公司最新权威推荐排行榜:覆盖工业 / 建筑 / 数据中心等领域 TOP5 优质企业综合测评与选型指南发电厂/燃气/全域增效/服务器节能公司推荐
  • 微算法科技(NASDAQ MLGO)探索全同态加密与安全多方计算融合,开启区块链隐私执行新时代
  • 国产SUB-1G芯片DP4363F支持119-1050mhz超低功耗 - 动能世纪
  • 2025 年棕刚玉源头厂家最新推荐排行榜:TOP 级生产厂家原料与烧结工艺权威解析,助力企业精准选购一级棕刚玉/棕刚玉磨料/优质棕刚玉/棕刚玉喷砂废料回收厂家推荐
  • 杀疯了!GitHub 发布 Copilot CLI!!!
  • 2025 年无尘金刚砂源头厂家最新推荐排行榜:权威精选企业产能与品质深度解析无尘金刚砂材料/无尘金刚砂批发/无尘金刚砂喷砂厂家推荐
  • 学习率调整策略
  • PySide6 之简易音乐播放器
  • langgraph-genui
  • web服务器配置步骤有哪些?如何建立一个web服务器
  • 题解:P10005 [集训队互测 2023] 基础寄术练习题
  • 详细介绍:Linux----gcc、g++的使用以及一些问题
  • 同步和互斥的基本概念
  • Sep 28
  • 图像采集卡:连接镜头与机器的“视觉神经”,释放工业智能核心动力
  • 2025 年生态木厂商最新推荐榜单:TOP 前五企业实力解析及厂商选择指南生态木方通/户外地板/装饰线条/隔断/背景墙厂商推荐
  • 盲盒一番赏小应用用户需求分析:从行为动机到功能诉求的深度拆解
  • 解题报告-泥路(muddyroad.*)
  • 洛谷P10112 [GESP202312 八级] 奖品分配
  • P10400 『STA - R5』消失的计算机
  • 2025 地坪研磨机厂家推荐权威推荐排行榜:品牌深度解析及格力 / 宁德时代合作案例速递水磨石/遥控式/座驾式/小型地坪研磨机厂家推荐
  • 2025 年最新推荐铝塑膜源头厂家权威排行榜:聚焦 3000㎡厂房与完整产业链的优质企业盘点复合/防锈防潮/木箱包装/设备包装铝塑膜厂家推荐
  • 2025 年真空袋生产厂家最新权威推荐排行榜:TOP 级企业工艺、服务及适配场景全景对比指南木箱/设备/海运防潮/铝塑/电柜真空袋厂家推荐
  • 《码界飞升传II:数据星辰异界问道》