以下文章来源于小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条评论, 我也要评论