校园活动
题目链接:nowcoder 215070
到主站看:https://blog.csdn.net/weixin_43346722/article/details/113063890
题目大意
有一堆数,要你分成尽可能多的段,使得每一段的值的和相同。
输出最多能分的段数,但如果只能分成一个组(就是所有人都在同一个组),就输出 -1。
思路
这道题我们用模拟来做。
因为看到所有值的和很小,我们考虑直接从小到大枚举分成的每一段的数的和是多少。
然后判断一下是否可以,可以就输出。因为所有值的和越小,分出来的段数就越多。
代码
#include<cstdio> using namespace std; int n, a[1001], r, sum; bool all0 = 1; char c; bool work(int now) {//从左往右扫,区间值的和等于要求的就到下一个区间 sum = 0; for (int i = 1; i <= n; i++) { sum += a[i]; if (sum > now) return 0;//无法组成,会超过 else if (sum == now) sum = 0; } return 1; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { c = getchar(); while (c < '0' || c > '9') c = getchar(); a[i] = c - '0'; if (all0 && a[i]) all0 = 0; r += a[i]; } if (all0) { printf("%d", n); return 0; } for (int i = 1; i <= r >> 1; i++)//枚举长度 if (r % i == 0) {//起码要能整除,不然不可能均分 if (work(i)) { printf("%d", r / i);//如果此长度可行,输出这个长度能分成的段数 return 0; } } printf("-1"); return 0; }