【AcWing】4366.上课睡觉

题目描述

解题思路

整体思路：

1. 性质：要实现最终每一堆的数量相同，那么每一堆的石子数量必须能够整除所有石子数量。
2. 把所有石子的数量求和（sum），并统计最多一堆石子的数量。
3. 因为只能合并成sum的因子，所以可以从小到大遍历sum的因子。
4. 判断因子的合法性：遍历每堆石子将其合并，如果某些连续的石子合并起来等于其因子，就继续合并下一堆；如果某些连续的石子大于其因子，直接遍历判断下一个因子。

代码实现

#include 
#include 
#include 
using namespace std;
const int N = 100010;
int n;
int w[N];// 检查因子是否合法
bool check(int cnt)
{for (int i = 0, s = 0; i < n; i ++){s += w[i];if (s > cnt) return false;if (s == cnt) s = 0;}return true;
}int main()
{int T;cin >> T;while (T --){cin >> n;int sum = 0;for (int i = 0; i < n; i ++){cin >> w[i];sum += w[i];}for (int i = n; i; i --)// sum / i 表示sum的一个因子if (sum % i == 0 && check(sum / i)){cout << n - i << endl;break;}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！