Sorting Pancakes

题意翻译

### 题意简述 有 $n$ 个箱子和 $m$ 个小球，初始时第 $i$ 个箱子有 $a_i$ 个小球。每次操作可以将**一个**小球移到相邻的箱子里。求要使得最终数组 $a_i\ge a_{i+1}$ 的最小操作次数。 ### 输入格式 第一行两个正整数 $n,m$。 第二行 $n$ 个非负整数 $a_i$。数据保证 $\sum a_i=m$。 ### 输出格式 输出一行一个非负整数，表示答案。 ### 数据规模 $1\le n,m\le 250$

题目描述

Nastya baked $ m $ pancakes and spread them on $ n $ dishes. The dishes are in a row and numbered from left to right. She put $ a_i $ pancakes on the dish with the index $ i $ . Seeing the dishes, Vlad decided to bring order to the stacks and move some pancakes. In one move, he can shift one pancake from any dish to the closest one, that is, select the dish $ i $ ( $ a_i > 0 $ ) and do one of the following: - if $ i > 1 $ , put the pancake on a dish with the previous index, after this move $ a_i = a_i - 1 $ and $ a_{i - 1} = a_{i - 1} + 1 $ ; - if $ i < n $ , put the pancake on a dish with the following index, after this move $ a_i = a_i - 1 $ and $ a_{i + 1} = a_{i + 1} + 1 $ . Vlad wants to make the array $ a $ non-increasing, after moving as few pancakes as possible. Help him find the minimum number of moves needed for this. The array $ a=[a_1, a_2,\dots,a_n] $ is called non-increasing if $ a_i \ge a_{i+1} $ for all $ i $ from $ 1 $ to $ n-1 $ .

输入输出格式

输入格式

The first line of the input contains two numbers $ n $ and $ m $ ( $ 1 \le n, m \le 250 $ ) — the number of dishes and the number of pancakes, respectively. The second line contains $ n $ numbers $ a_i $ ( $ 0 \le a_i \le m $ ), the sum of all $ a_i $ is equal to $ m $ .

输出格式

Print a single number: the minimum number of moves required to make the array $ a $ non-increasing.

输入输出样例

输入样例 #1

6 19
5 3 2 3 3 3

输出样例 #1

2

输入样例 #2

3 6
3 2 1

输出样例 #2

0

输入样例 #3

3 6
2 1 3

输出样例 #3

1

输入样例 #4

6 19
3 4 3 3 5 1

输出样例 #4

3

输入样例 #5

10 1
0 0 0 0 0 0 0 0 0 1

输出样例 #5

9

说明

In the first example, you first need to move the pancake from the dish $ 1 $ , after which $ a = [4, 4, 2, 3, 3, 3] $ . After that, you need to move the pancake from the dish $ 2 $ to the dish $ 3 $ and the array will become non-growing $ a = [4, 3, 3, 3, 3, 3] $ .