网站建设线框图,企业vi品牌设计公司,设计网站报价,遵义哪里有做网站的[题目概述]
有 n 个小朋友坐成一圈#xff0c;每人有 a[i] 个糖果。 每人只能给左右两人传递糖果。 每人每次传递一个糖果代价为 1。 求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n#xff0c;表示小朋友的个数。 接下来 n 行#xff0c;每行一个…[题目概述]
有 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 algorithmusing 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;
}本题的分享就结束了贪心感觉比其他难很多这就是推出来结论就能做推不出来就根本不会上下浮动很大很难学。
