以下文章来源于小K算法 ，作者小K算法
小K算法 .
曾就职华为和美团，中山大学数学与计算机系本科，专注分享数学、算法、科学等硬核知识
来自公众号：小K算法
故事起源
编号为1的堆上取的纸牌只能移到编号为2的堆上
编号为N的堆上取的纸牌只能移到编号为N-1的堆上
其他堆上取的纸牌可向左右相邻堆移动
那N堆纸牌是不是移动次数也在0~(N-1)次就可以完成呢？继续往下分析。
0次：3堆都为平均数
1次：第一堆或者第三堆为平均数
2次：其它情况
这样两边其实可以看成两个完全独立的子问题。
如果不考虑移动次数肯定可以做到，那能否通过一次移动使子区间可以分割开呢？
区间[1,i+1]均摊后大于平均数(只有扫到末尾才可能刚好等于平均数)，这时只需从上移动区间[1,i]还缺少的x个到上，使得区间[1,i]刚好够分，这样一次移动也能把区间分割成两个更小的子区间。
即移动一次最多一分为二，不可能一分为三，那么有X堆的子区间最少也得移动X-1次。
我们不需要真正去移动，只需要求出最少的次数。所以如果初始区间可以分割为Y个子区间，那么整个区间最少移动就是N-Y次。
int main() {
int n, a[100], sum = 0, interval = 0;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum += a[i];
}
int avg = sum / n, last = -1;
sum = 0;
for (int i = 0; i < n; ++i) {
sum += a[i];
if (sum == (i - last) * avg) {
interval++;
sum = 0;
last = i;
}
}
cout << n - interval << endl;
return 0;
}
实现代码非常简单，但思考过程并不简单，需要找出问题的本质规律，要证明算法的正确性，这个还是有一些思考量在里面的。大家跟着小K的思路多思考，勤用脑，总有一天你会感叹：原来都是套路啊，哈哈。
文章首发平台：微信公众号【小K算法】。
网友评论已有0条评论, 我也要评论