C26C:Equal Sequence

http://poj.openjudge.cn/practice/C26C/

C++

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int64 calc(const vector<int64>& a, int64 target) {
    int64 ans = 0;

    for (int64 x : a) {
        int64 d = target - x;

        if (d <= 0) {
            ans += -d;
        } else {
            if (d % 2 == 0) {
                ans += d / 2;
            } else {
                ans += (d + 3) / 2;
            }
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    int k = (2 * n + 2) / 3; 
    // k = ceil(2n / 3), 1-indexed

    int64 q = a[k - 1];

    cout << min(calc(a, q - 1), calc(a, q)) << '\n';

    return 0;
}

这道题目是一道典型的贪心算法题，其核心在于找到一个目标值 $q$ ，使得所有数字变换到 $q$ 的总代价最小。

由于增加数值和减少数值的代价不对等（减少 1 的代价是 1，增加 1 的代价大约是 0.5），最优解不再是传统意义上的中位数（ $1 / 2$ 处），而是偏移到了序列的 $2 / 3$ 处。

Python 代码实现

python

import sys

def calc(a, target):
    """
    计算将数组 a 中所有元素变换到 target 的总代价
    """
    ans = 0
    for x in a:
        d = target - x
        if d <= 0:
            # 情况 1: x >= target
            # 数值需要变小，每减少 1 单位代价为 1
            ans += -d
        else:
            # 情况 2: x < target
            # 数值需要变大。根据题目逻辑：
            # 如果差值 d 是偶数，代价为 d / 2
            # 如果差值 d 是奇数，代价为 (d + 3) / 2
            if d % 2 == 0:
                ans += d // 2
            else:
                ans += (d + 3) // 2
    return ans

def main():
    # 使用 sys.stdin.read().split() 快速读取大规模数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    a = list(map(int, input_data[1:n+1]))
    
    # 第一步：排序。为了通过中位数性质找到最优解
    a.sort()
    
    # 第二步：确定目标值 q
    # 在代价不对等的情况下，最优解会向代价高的方向偏移
    # 这里的 k 经过数学推导约为 (2n)/3 的位置
    k = (2 * n + 2) // 3 
    
    # 取排序后第 k 个数作为基准
    q = a[k - 1]
    
    # 第三步：计算 q 和 q-1 两种情况下的代价，取最小值
    # 因为代价函数在 q 附近可能有波动，检查相邻点更稳妥
    res = min(calc(a, q - 1), calc(a, q))
    
    print(res)

if __name__ == "__main__":
    main()

代码解读

1. 代价函数 `calc` 的逻辑

题目定义的变换规则隐含在 calc 函数中：

减小数值 ( $x > t a r g e t$ )：代价是线性的，即 x - target。
增大数值 ( $x < t a r g e t$ )：代价是非线性的。
- 例如：差 2 的代价是 1，差 4 的代价是 2。这说明增加数值时，每 2 个单位才花费 1 个单位的代价。
- 奇数时的 (d+3)//2 是为了处理特定的补偿逻辑。

2. 为什么取 $2 / 3$ 处的值？

在经典的“货仓选址”问题中，如果移动代价是对称的（上升 1 和下降 1 代价一样），最优解是中位数（ $1 / 2$ 处）。本题中：

下降代价系数为 $1$ 。
上升代价系数约为 $1 / 2$ （增加 2 耗费 1）。
根据加权中位数理论，最优解 $q$ 应该满足：小于 $q$ 的元素权重之和与大于 $q$ 的元素权重之和大致相等。
这里的比例大约是 $1 : 0.5$ ，即 $2 : 1$ 。因此在总数 $n$ 中，划分点大约在 $2 n / (2 + 1) = 2 / 3$ 处。

3. Python 性能优化

使用 sys.stdin.read().split()：比多次调用 input() 快得多，适用于处理 POJ 或 OpenJudge 上万级别的数据输入。
// 运算符：Python 中的整除运算符，确保结果为整数。
if __name__ == "__main__":：标准的 Python 程序入口写法。

C26C:Equal Sequence ​

Python 代码实现 ​

代码解读 ​

1. 代价函数 calc 的逻辑 ​