13026: 【原3026】欢总的传家宝

题目

题目描述

author: 廖予科 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3026

Description

昨日深夜，欢总于家中床下偶得其传家宝—一条由珍贵珠宝组成的金项链，由于年代久远，项链的链扣已经坏掉，项链变成一条直链，而不再是一个环（图为欢总显得气急败坏），这条项链上面的珠宝价值并不完全相同，每一颗都有表征其价值的一个自然数权值。现欢总准备将这条项链切成若干份来送给他的一些女朋友（每个女朋友只送一份），每一份包含若干颗连续的珠宝，为了避免他的女朋友们争风吃醋，每份的珠宝权值之和要求相等，作为一名有野心的男人，欢总希望能取悦尽量多的女朋友。

对每一条给定的直链，你的任务是写一个程序帮助欢总决定他能取悦的女朋友的数量的最大值。

例：对于此条直链 1，1，2，2，2 有如下几种切法（1，1）（2）（2）（2） （1，1，2）（2，2） （1，1，2，2，2） 这三种切法能分别取悦4，2，1名女朋友，所以所能取悦的女朋友的数量最大值为4

Input Format

第一行是一个正整数P(1 <= P <= 1000 )表示一共有多少根项链,接下来会有P组数据，每一组按如下方式给出：每组的第一行包含两个整数，第一个是组号N(1 <= N <= P)，第二个是这根项链上的珠宝数M(1 <= M <= 10000)，从第二行开始是M个正整数，每行20个，每两个整数之间由一个空格隔开，最后一行可能会少于20个。

Output Format

对于每一组数据，按如下方式输出两个整数作为一行：第一个为组号，第二个为用这个项链欢总所能取悦的女朋友的最大数量，并将两个整数用一个空格隔开。

Hint

所有的计算均可在long long范围内进行

Sample Input

3 
1 6 
2 5 1 3 3 7 
2 6 
1 2 3 4 5 6 
3 20 
1 1 2 1 1 2 1 1 2 1 
1 2 1 1 2 1 1 2 1 1

Sample Output

1 3
2 1
3 13

ligongzzz's solution

#include <iostream>
#include <vector>
using namespace std;

int cal(const vector<long long>& vdata, long long total) {
    long long base = 0;
    for (int pos = 0; pos < vdata.size(); ++pos) {
        bool flag = true;
        base += vdata[pos];

        if (total % base)
            continue;

        long long temp = 0;
        int cnt = 0;
        for (int i = 0, j = 0; j < vdata.size(); ++j) {
            temp += vdata[j];
            if (j == vdata.size() - 1) {
                if (temp != base) {
                    flag = false;
                    break;
                }
            }

            if (temp == base) {
                temp = 0;
                i = j + 1;
                ++cnt;
            }
            else if (temp > base) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return cnt;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int p;
    cin >> p;

    for (; p; --p) {
        int n, m;
        cin >> n >> m;

        vector<long long> vdata(m);

        long long total = 0;
        for (int i = 0; i < m; ++i) {
            cin >> vdata[i];
            total += vdata[i];
        }

        cout << n << " " << cal(vdata, total) << "\n";
    }

    return 0;
}