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

21 ACwing 289 环路运输 题解

环路运输

题面

在一条环形公路旁均匀地分布着 N 座仓库,编号为 1∼N,编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 \(dist(i,j)=min(|i−j|,N−|i−j|)\),也就是逆时针或顺时针从 i 到 j 中较近的一种。

每座仓库都存有货物,其中编号为 i 的仓库库存量为 \(A_i\)

在 i 和 j 两座仓库之间运送货物需要的代价为 \(A_i+A_j+dist(i,j)\)

求在哪两座仓库之间运送货物需要的代价最大。

\(2 \le N \le 10^6\)

\(1 \le A_i \le 10^7\)

题解

这道题朴素的枚举是 \(O(N^2)\) ,所以要优化

因为题目给定的实际上是个环形结构,那么我们可以将其转化成一个线性结构,也就是常用的断环为链技巧复制一倍放末尾

那么对于 \(1 \le j < i \le N \times 2\)

\(i - j \le \frac N 2\) 那么 \(dist(i,j) = i - j\)

否则就对应着在 \(j + N \to i\) 之间的距离,也就是 \(N + j - i = N - (i - j) < \frac N 2\)

这样问题就变成了在一个长度为 \(2N\) 的序列上找到满足 \(1 \le j < i \and i - j \le N / 2\)\(i,j\)\(A_i + A_j + i - j\) 的最大值

所以我们可以枚举 \(i\) ,求出 \(\max_{i - \frac N 2 \le j < i} \{ A_i + A_j + i - j \} = \max_{i - \frac N 2 \le j < i} \{ A_j - j \} + A_i + i\) ,用单调队列即可 \(O(N)\) 求解

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 2e6 + 10;int n, a[N];
int q[N];int main () {cin >> n;for (int i = 1; i <= n; i ++) {cin >> a[i];}for (int i = n + 1; i <= n * 2; i ++) {a[i] = a[i - n];}int ans = 0;int h = 1, t = 0;for (int i = 1; i <= n * 2; i ++) {while (h <= t && q[h] < i - n / 2) h ++;if (h <= t) ans = max (ans, a[i] + i + a[q[h]] - q[h]);while (h <= t && a[q[t]] - q[t] < a[i] - i) t --;q[++t] = i;}cout << ans << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=25026

相关文章:

  • 26 UVA1630 串折叠 Folding 题解
  • 13 ACwing 283 Polygon 题解
  • 12 ACwing 282 石子合并 题解
  • 11 ACwing 281 Coins 题解
  • 某中心科学家荣获多项计算机技术大奖
  • FFT
  • 4 ACwing 274 Mobile Service 题解
  • 3 ACwing 273 Making the Grade 题解
  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记