20241006每日一题洛谷P1031

对题目第一印象：贪心吧，或者纯模拟

第一次贪心，由于左右端堆只能想内一堆移动，遂放弃

第一次模拟，开多个数组，（可能还要用递归？），遂放弃

于是求助如来佛祖：

从逻辑上可以看出，第一堆缺或者多的牌只能移动到第二堆上

当第一堆达到期望值时，第一堆便不能再做操作，于是，可以将第二堆作为第一堆来处理

（有点像递归？）

举一个简单的例子：

4
9 8 17 6

期望值为：reduce()/4=10;

第一堆：需要1，则第二堆给第一堆1

第二堆：需要2+1，则第三堆给第二堆3

第三堆：需要-7+3，则第四堆给第三堆-4

第四堆：需要4，上一步给出的-4相当于给入的4，则第四堆也达到期望值

实现代码如下

/////

int main() {
	int n,sum=0,cnt=0;
        int a[110];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		sum += a[i];
	}
	sum /= n;//计算期望值
	for (int i = 0; i < n; i++) {
		if ((a[i] - sum) != 0) {
			a[i + 1] += a[i] - sum;//计算期望值差
			cnt++;//操作数
		}
	}
	printf("%d", cnt);
	return 0;
 }

/////