糖果传递

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 939 字

环形均分纸牌，取盈亏前缀的中位数

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1432
// 题意：n 个小朋友围成一圈，每人只能把糖果传给左右邻居，传一个代价为 1，求让所有人糖果数相等的最小代价。
// 思路：拆环成链后用中位数结论。
// 1. 设平均数为 avg，令 c[i] 为前 i 个人相对平均数的累计盈亏。
// 2. 环形均分纸牌的最小代价等于 sum |c[i] - c 的中位数|。
// 3. 用 nth_element 在线性时间求出中位数，数据量 n 可达 1e6。
// 复杂度：O(n) 平均时间 / O(n) 空间
// 易错点：糖果总数可能不能被 n 整除时题目保证有解，但累加和一定要用 long long。
// 易错点：c 数组一共 n 个（含最后一个为 0 的那项），不要把最后一项漏掉。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    if(!(cin >> n)) return 0;
    vector<long long> a(n), c(n);
    long long sum = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }
    long long avg = sum / n;
    long long pre = 0;
    for(int i = 0; i < n; i++){
        pre += a[i] - avg;
        c[i] = pre;
    }
    nth_element(c.begin(), c.begin() + n / 2, c.end());
    long long mid = c[n / 2];
    long long ans = 0;
    for(int i = 0; i < n; i++) ans += llabs(c[i] - mid);
    cout << ans << "\n";
    return 0;
}

糖果传递

正文

一本通·提高篇的其它内容