平数

GitHub跳转原题关系图返回列表

统计正数之和 P 与负数绝对值之和 N，两条下界不等式相加得答案 max(P,N)，配对构造恰好达到该下界。

OJ: roj

题目 ID: 8000

难度:普及-

标签:入门数学贪心python

创建: 2026-10-02 16:22

更新: 2026-10-06 16:42

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

给定 nn 个整数 a1,…,ana_1, \dots, a_n。每次操作可任选其一：任选一个数加 1 或减 1；或任选两个不同下标 i≠ji \neq j，让其中一个加 1、另一个减 1。两类操作各算一次，求把所有数同时变成 0 所需的最少操作次数。

输入格式：第一行整数 nn，第二行 nn 个整数。数据范围：n≤105n \le 10^5，∣ai∣≤105|a_i| \le 10^5。输出格式：一行一个整数。样例输入 5 与 1 2 -4 -1 8，样例输出 11。

思路

记正数之和为 PP、负数绝对值之和为 NN：单个操作不改总和，成对操作只有"正挪给负"每次减少绝对值和 2，两条下界不等式 x≥∣P−N∣x \ge |P-N| 与 x+2y≥P+Nx+2y \ge P+N 相加得 x+y≥max⁡(P,N)x+y \ge \max(P,N)。按"先配对 min⁡(P,N)\min(P,N) 次、再单个操作清掉剩余 ∣P−N∣|P-N| 次"构造恰好达到该下界，所以答案就是 max⁡(P,N)\max(P, N)。一遍扫描统计 PP、NN 即可，和最大可达 101010^{10} 要用 long long。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://roj.ac.cn  https://rbook.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 16:23
# update_at: 2026-10-02 16:23

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 数的个数
    values = [next(data) for _ in range(n)]  # n 个数

    sp = sum(v for v in values if v > 0)   # 正数之和 P
    sn = sum(-v for v in values if v < 0)  # 负数绝对值之和 N

    # 设 x 次单个操作、y 次成对操作：单个操作不改变 P-N，故 x >= |P-N|；
    # 每次操作至多让 P+N 减 2，故 x+2y >= P+N。
    # 两式相加：2(x+y) >= (P+N)+|P-N| = 2*max(P,N)，而先配对 min(P,N) 次、
    # 再单个消掉 |P-N| 恰好做到 max(P,N) 次。
    print(max(sp, sn))


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:42
 * update_at: 2026-10-06 16:42
 */

// 把所有数变成 0 的最少操作次数：
// 记 P = 正数之和，N = 负数绝对值之和。
// 下界：两类不等式相加得 x + y >= max(P, N)；
// 构造：先配对 min(P, N) 次（正数挪 1 给负数），再单个操作清掉剩余 |P - N|，
// 恰好达到 max(P, N)，所以答案就是 max(P, N)。

#include <cstdio>

typedef long long ll;

const int MAXN = 100005;

int n;
ll a[MAXN]; // a[i] 存第 i 个数

int main() {
    scanf("%d", &n);
    ll pos = 0, neg = 0; // pos = 正数之和 P，neg = 负数绝对值之和 N
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        if (a[i] > 0)
            pos += a[i];
        else
            neg += -a[i]; // 负数取绝对值累加（0 也无害）
    }
    // 答案为两者较大值；|a_i| <= 1e5、n <= 1e5，和最大 1e10，必须用 ll
    ll ans = pos > neg ? pos : neg;
    printf("%lld\n", ans);
    return 0;
}