AcWing 122 糖果传递（贪心）
[题目概述]
有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n，表示小朋友的个数。
接下来 n 行，每行一个整数 a[i]，表示第 i 个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数，表示最小代价。
数据范围
1 ≤ n ≤ 1000000 , 1 ≤ n ≤ 1000000, 1≤n≤1000000,
0 ≤ a [ i ] ≤ 2 × 1 0 9 0 ≤ a[i] ≤ 2×10^9 0≤a[i]≤2×109
数据保证一定有解。
输入样例：
4
1
2
5
4
输出样例：
4
贪心法感觉就是在解数学题，将题目抽象成一个数学模型，推出来结论就能写，推不出来就废。
我们可以将每次传递的糖果用x数组表示
然后就开始了数学推导
然后我们就将及其复杂的问题化成了一个简单的模型。
- 完整代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1000010;int a[N], n;
long long c[N];
long long sum, avg, ret;
int main(){cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];sum += a[i];}avg = sum / n;// 求c数组for(int i = n; i > 1; i --){c[i] = c[i + 1] + avg - a[i];} sort(c + 1, c + n + 1);// 求最小价值for(int i = 1; i <= n; i ++){ret += abs(c[i] - c[(n + 1) / 2]);}cout << ret << endl;return 0;
}
- 本题的分享就结束了，贪心感觉比其他难很多，这就是推出来结论就能做，推不出来就根本不会，上下浮动很大，很难学。