算法-贪心-122. 糖果传递

题目

有n个小朋友坐成一圈，每人有a[i]个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为1。

求使所有人获得均等糖果的最小代价。

输入格服务器托管网式

第一行输入一个正整数n，表示小朋友的个数。

接下来n 行，每行一个整数a[i]，表示第i 个小朋友初始得到的糖果的颗数。

输出格式

输出一个整数，表示最小代价。

数据范围

1≤n≤1000000,
0≤a[i]≤210的9次方,
数据保证一定有解。

输入样例：

4
1
2
5
4

输出样例：

4

思路

1. 糖果不会凭空增加或者消失；本题只考虑一定有解的情况，也就是总数一定能够整除n；不会出现环形给的情况：a->b->c->a;
2. 数据范围是1e6,所以要做到nlogn或者是O(n)的情况;
3. 建立数学模型：
   1. xi可正可负；
   2. 目标：使所有xi的绝对值相加之和最小
   3. 限制：

      

   4. n-1个独立的方程，n个未知数，可以用某一个的x来表示其他的x
      
   5. 目标函数转化为：（类似上一题的货物运输：求中位数+求Ci）
      
   6. 

代码

n = int(input())
a=[int(input()) for _ in range(n)]
# print(l1)
c=[0 for _ in range(n)]
avg=sum(a)//n
for i in range(n-1,0,-1):
    c[i-1] = c[i]+avg-a[i] 
    # 注意下标范围是从0开始的，题解下标从1开始
c.sort()
res=0
for i in range(n):
    res+=abs(c[i]服务器托管网-c[(n-1)//2])
print(res)

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 计算机视觉的应用23-OpenAI发布的文本生成视频大模型Sora的原理解密

大家好，我是微学AI，今天给大家介绍一下计算机视觉的应用23-OpenAI发布的文本生成视频大模型Sora的原理解密。本文概况性地将Sora模型生成视频主要分为三个步骤：视频压缩网络、空间时间潜在补丁提取以及视频生成的Transformer模型。 文章目录 一…