洛谷-P3650 [USACO1.3] 滑雪课程设计 Ski Course Design 题解-北京尧图网络

题意概述给定一个长度为n nn的数列{ a i } \{a_i\}{ai}将a i a_iai改为b bb所需的代价是( a i − b ) 2 (a_i-b)^2(ai−b)2。求使得max ⁡ { a i } − min ⁡ { a i } ≤ 17 \max\{a_i\}-\min\{a_i\}\le17max{ai}−min{ai}≤17所需的最小代价。解题思路考虑三分法。如果不会三分法右转 OI Wiki 学一学。设要将数列的所有元素修改到[ x , x 17 ] [x,x17][x,x17]区间内则代价即为关于x xx的函数f ( x ) f(x)f(x)。问题转化求f ( x ) f(x)f(x)在[ min ⁡ { a i } , max ⁡ { a i } − 17 ] [\min\{a_i\},\max\{a_i\}-17][min{ai},max{ai}−17]区间上的最小值。显然若[ x , x 17 ] [x,x17][x,x17]的范围超出了数列的取值范围则一定不会更优。由题意得f ( x ) ∑ i 1 n c o s t i ( x ) f(x)\sum_{i 1}^{n}cost_i(x)f(x)i1∑ncosti(x)其中c o s t i ( x ) cost_i(x)costi(x)为元素a i a_iai产生的代价是关于x xx的函数为c o s t i ( x ) { ( a i − x ) 2 ( a i x ) , 0 ( x ≤ a i ≤ x 17 ) , ( a i − x − 17 ) 2 ( a i x 17 ) . cost_i(x) \begin{cases} (a_i - x)^2(a_ix),\\ 0(x\leq a_i\leq x 17),\\ (a_i - x - 17)^2(a_ix 17). \end{cases}costi(x)⎩⎨⎧(ai−x)20(ai−x−17)2(aix),(x≤ai≤x17),(aix17).c o s t i ( x ) cost_i(x)costi(x)的图像如下图所示很显然这是一个单谷函数。因为单谷函数的和还是单谷函数所以f ( x ) f(x)f(x)也是单谷函数。于是可以直接使用三分法求解最小值。时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)。Code#includeiostreamusingnamespacestd;constintN1000;constintINF0x3f3f3f3f;inta[N],n;intf(intx){ints0;for(inti0;in;i){if(a[i]x)s(x-a[i])*(x-a[i]);elseif(a[i]x17)s(a[i]-x-17)*(a[i]-x-17);}returns;}intmain(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);intlINF,r-INF,m1,m2;cinn;for(inti0;in;i){cina[i];lmin(l,a[i]);rmax(r,a[i]);}r-17;while(lr){m1(lr1),m2m11;if(f(m1)f(m2))rm2-1;elselm11;}coutf(l);return0;}Update 2025.2.11笔误单峰函数→ \to→单谷函数。Update 2025.6.15更换图片更改图片与文字间距。Update 2025.6.16修改部分公式格式。Update 2025.12.6微调格式优化语言表达。

洛谷-P3650 [USACO1.3] 滑雪课程设计 Ski Course Design 题解

相关推荐

用Codex和Chromatic复刻街机游戏：AI辅助开发实践记录

洛谷-B3930 [GESP202312 五级] 烹饪问题题解

【opencv】Opencv python: seamlessClone泊松融合 (我把Lena变成了彼岸花怪/(ㄒoㄒ)/~~)

更多资讯

智学文枢：学生与习题的状态中枢

FST: Fast-Thinking Slow-Thinking Task Decomposition for LLMs (arXiv:2504.08690)

电商优惠券系统实战：满减活动设置与商城营销防薅羊毛完整方案

熬夜伤卵巢，不只是激素：2026 两项研究都指向 NAD⁺

R 语言实战：从数据处理到可视化的完整实例

ESP32 CSI 快速上手指南：用两块开发板跑通 Wi-Fi 感知链路

今日更新

Verilog实现FPGA密码锁：矩阵键盘与状态机设计实战

数据服务监控运维实战：从指标体系到告警治理与故障排查

FreeRTOS任务通知实战详解：内核原理、API与避坑指南

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？