校园活动

题目链接: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;
}