把龙虎气势差折叠成带符号的 delta = Σ c_i×(m-i)，再枚举投放位置 p 取 |delta + s_2×(m-p)| 最小的最小编号。
OJ: roj
题目 ID: 3655
难度:入门
标签:枚举前缀和思想模拟python
创建: 2026-10-02 13:30
更新: 2026-10-06 16:00
题目描述
线段上有 n 个兵营，第 i 个有 c_i 位工兵。以 m 号兵营为界，左侧（p<m）属龙方，右侧（p>m）属虎方，m 号不属于任何一方；兵营 p 的气势为 c_p × |p-m|，一方势力为所属兵营气势之和。先在 p_1 号兵营增加 s_1 位工兵，再把 s_2 位工兵全部投放到某个兵营 p_2，使龙、虎两方势力之差的绝对值最小，输出最优的 p_2（并列取最小编号）。
输入第一行 n，第二行 n 个整数 c_i，第三行四个整数 m, p_1, s_1, s_2；输出一个整数 p_2。数据范围：1 < m < n ≤ 10^5，c_i, s_1, s_2 ≤ 10^9。样例 1 输入 6 / 2 3 2 3 2 3 / 4 6 5 2，输出 2；样例 2 输入 6 / 1 1 1 1 1 16 / 5 4 1 1，输出 1。
思路
把龙虎气势差折叠成一个带符号的和 δ = Σ c_i×(m-i)：p<m 的项为正（龙），p>m 的项为负（虎），p=m 恰为 0。投放 s_2 人到 p 后的差距为 |δ + s_2×(m-p)|，从左到右扫一遍取最小值，并列取最小编号；初值取 p=m 即“不改变气势”。气势差可达约 2×10^19，需用 __int128。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47
import sys
def momentum(pos: int, m: int, count: int) -> int:
"""count 位工兵落在 pos 号兵营产生的带符号气势：龙方为正、虎方为负。"""
return count * (m - pos)
def best_camp(delta: int, m: int, s2: int, n: int) -> int:
"""在气势差 delta（龙-虎）基础上投放 s2 人，返回使 |delta| 最小的兵营编号。"""
ans, best = m, abs(delta) # 不投也允许（p2 = m），初值就是"投到 m"的效果
for p in range(1, n + 1):
cur = abs(delta + momentum(p, m, s2))
if cur < best:
ans, best = p, cur
return ans
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
c = [next(data) for _ in range(n)]
m, p1, s1, s2 = next(data), next(data), next(data), next(data)
c[p1 - 1] += s1 # 天降神兵：先落位 s1
# 龙方气势为正、虎方气势为负，二者之差就是 delta（m 号兵营两侧贡献都为 0）
delta = sum(momentum(pos, m, c[pos - 1]) for pos in range(1, n + 1))
print(best_camp(delta, m, s2, n))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 16:00
* update_at: 2026-10-06 16:00
*/
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
ll c[MAXN]; // c[i] 表示第 i 个兵营的工兵数（包含天降神兵后的数量）
// 气势差最大约 c_i * |m-i| * n ≈ 2e19，超过 long long 上限，故用 __int128 保存。
// 返回 __int128 的绝对值。
__int128 i128_abs(__int128 x) {
if (x < 0) return -x;
return x;
}
// 返回 count 位工兵落在 pos 号兵营产生的带符号气势：龙方为正、虎方为负。
__int128 signed_momentum(ll count, ll pos, ll m) {
__int128 cnt = count;
return cnt * (m - pos);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &c[i]);
}
ll m, p1, s1, s2;
scanf("%lld %lld %lld %lld", &m, &p1, &s1, &s2);
c[p1] += s1; // 天降神兵：先在 p1 号兵营补上 s1 人
// delta = 龙方气势 - 虎方气势 = sum c[i] * (m - i)
// p < m 时为正（龙），p > m 时为负（虎），p = m 时恰为 0
__int128 delta = 0;
for (int i = 1; i <= n; i++) {
delta += signed_momentum(c[i], i, m);
}
// 枚举投放位置，取使 |delta + s2*(m-p)| 最小的最小编号；
// 初值取 p2 = m（相当于不改变气势），并保证并列时保留更左的编号
ll ans = m;
__int128 best = i128_abs(delta);
for (int p = 1; p <= n; p++) {
__int128 cur = i128_abs(delta + signed_momentum(s2, p, m));
if (cur < best) {
best = cur;
ans = p;
}
}
printf("%lld\n", ans);
return 0;
}
