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

P11854 [CSP-J2022 山东] 宴会

题目传送门

当时这个题是我考试题,考试的时候感性理解出来的三分做法。

首先咱感性理解一下,当\(x_0\)位于左边无穷远处时,答案是个很大的数。

然后随着\(x_0\)从左向右移动,答案呈递减趋势。当\(x_0\)到达答案那个点时,距离最小。然后\(x_0\)接着向右移动,答案又递增。当\(x0\)位于右侧无穷远处时,答案又会趋近于无穷大。

所以我们猜想,\(ans\)\(x_0\)变化的函数先递减再递增。当\(x_0\)位于谷底时,\(ans\)就会取最小值。

接下来我们简单证明一下结论。

首先我们设\(i\)到集合地点所需时间关于\(x_0\)的函数为\(f(x_0)\)。显然\(f(x_0)=|x_0-x_i|+t_i\),图像如下:

P11854_1_1

这是一个折线。对于其他的\(i\),也应该是这样的折线。我们把所有的\(n\)条折线画在同一平面直角坐标系中,大概这样:

P11854_2

而对于一个确定的\(x_0\),聚集时间就是这一坨函数里\(x_0\)对应的因变量的最大值,对应到图像里就是\(x=x_0\)与各个图像交点里最高的点的纵坐标。

P11854_3

至于聚会时间关于\(x_0\)的函数图像,很明显就是对于每个横坐标\(x_0\)都取一下最大值得到的点组成的图像。比如这样。

P11854_4

看起来,对于这种情况来说是个折线。但是如何说明其他情况也是折线呢?

我们把这个过程看作一个函数图像两两合并的过程,也就是对于两个函数做上面的过程。这样事情就会简单很多,因为它们的斜率相同,位置关系无非是包含和相交两种。

如果是包含的话,显然合并后结果就是上面的函数。这种情况下两根折线合并后还是折线。

P11854_5

如果是相交的话,各取两个函数比较高的线,最终还是个折线。

P11854_6

所以折线间两两合并,最终结果还是折线,也就证明了我们可以用三分解决本题。

代码:

P11854
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();} while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}const int N=1e5+5;
const int inf=1e16;
const double sta=1e-5;
const double STA=0.01;
int T,n,pos[N],t[N];inline double f(double x){double ans=0;for(int i=1;i<=n;i++){ans=max(ans,fabs(pos[i]-x)+t[i]);}return ans;
}signed main(){T=read();while(T--){n=read();int mi=inf,ma=0;for(int i=1;i<=n;i++){pos[i]=read();mi=min(mi,pos[i]);ma=max(ma,pos[i]);}for(int i=1;i<=n;i++){t[i]=read();}//实数三分 double l=mi,r=ma;//显然答案不会在这个区间外 while(r-l>sta){double lmid=l+(r-l)/3,rmid=r-(r-l)/3;double ans1=f(lmid),ans2=f(rmid);//f(x0):求聚会时间 if(ans1>ans2){l=lmid;}else{r=rmid;}}//底下是自制的一个判断整数//具体来说,如果最终结果与它相邻的两个整数的误差不超过允许的范围,那我们就认为它是整数,否则就是小数 double ll=floor(l);double lll=ceil(l);if(STA>l-ll){int ans=ll;printf("%lld\n",ans);}else if(STA>lll-l){int ans=lll;printf("%lld\n",ans);}else{printf("%.1lf\n",l);}}return 0;
} 
http://www.hskmm.com/?act=detail&tid=20101

相关文章:

  • 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:数据星辰异界问道》
  • Win FAQ
  • 结论(数学)
  • loki收集容器日志
  • Xcode 火焰图