c++【一维数组】数字分组

Question

我的方法时间超限，求更优解法
我的解题思路请见代码注释
题目描述
小明的数学计算能力超强，常常在同学们面前表面得很骄傲。数学科代表实在看不下去了，决定出道很麻烦的题，好好“折磨”他一下。
数学科代表决定给他一些数，让他分组。从第一个数开始分组，且每组必须是连续的一段数，要求每组和相等，问每组和最小可以是多少。（当然这些数一定可以被分组，大不了直接分成一组。）

输入
第一行为一个数N

第二行为N个整数（每个数均小于等于1000），两个数间用空格隔开。

输出
一行，最小的和

样例输入
6
2 5 1 3 3 7

#include<iostream>
using namespace std;
long long n,a[1000002];
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)    //输入 
    {
        cin>>a[i];
    }
    for(long long sum=0;;sum++)    //分组的和，从小到大 
    {
        long long s=0,check=0;    //一个记录每一个分组的和，一个判断 
        for(long long i=1;i<=n;i++)
        {
            s+=a[i];    //进入分组 
            if(s==sum)    //如果分其中一个组的和s相等sum，找下一个分组，和重新变为0 
            {
                s=0;
                continue;
            }
            if(s>sum||(i==n&&s<sum))    //如果其中一个分组的和s超过sum 或者 
            {                            //到了最后一个数时 s不满sum，说明条件不成立
                check=1;
                break;
            }
        }
        if(check==0)    //直接输出，每组和一定最小，见第11行 
        {
            cout<<sum;
            return 0;
        }
    }
    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

解决问题一共有两种方法，一种是暴力解法，一种是动态规划。

暴力解法

使用暴力解法的思路是枚举所有可能的和，并判断是否满足题目要求。具体的步骤如下：

1. 遍历所有可能的和sum（从0到数组元素之和），对于每个sum，再遍历数组元素，累加元素值，直到累加和达到sum。
2. 在累加元素值的过程中，如果发现累加和sum超过了目标和，则直接跳出内层循环。
3. 如果累加和sum等于目标和，说明找到了一个分组，记录下当前的和sum，并重置累加和为0，继续遍历。
4. 最后输出最小的和。

下面是使用暴力解法实现的代码：

#include<iostream>
using namespace std;

int main()
{
    int n,a[1000002];
    cin>>n;
    for(int i=1;i<=n;i++)    //输入 
    {
        cin>>a[i];
    }
    int minSum = INT_MAX;
    for(int sum=0;;sum++)    //分组的和，从小到大 
    {
        int s=0,check=0;    //一个记录每一个分组的和，一个判断 
        for(int i=1;i<=n;i++)
        {
            s+=a[i];    //进入分组 
            if(s==sum)    //如果分其中一个组的和s相等sum，找下一个分组，和重新变为0 
            {
                s=0;
                continue;
            }
            if(s>sum||(i==n&&s<sum))    //如果其中一个分组的和s超过sum 或者 
            {                            //到了最后一个数时 s不满sum，说明条件不成立
                check=1;
                break;
            }
        }
        if(check==0)    //直接输出，每组和一定最小，见第11行 
        {
            minSum = sum;
            break;
        }
    }
    cout<<minSum;
    return 0;
}

动态规划

使用动态规划的思路是先计算出数组元素之和total，然后创建一个二维数组dp，dp[i][j]表示将数组前i个元素划分为j个分组时，每个分组的和的最小值。 具体的步骤如下：

1. 遍历数组元素，累加得到数组元素之和total。
2. 初始化二维数组dp，大小为[n+1][n+1]，并将所有元素初始化为最大整数。
3. 初始化dp[0][0]为0。
4. 遍历1到n，对于每个i，遍历1到i，对于每个j，计算dp[i][j]。
   • dp[i][j]的值是数组前i个元素中的一个分组，且第j个分组的和的最小值。因此，需要遍历所有可能的划分点k（k从j-1到i-1），计算dp[i][j]的最小值，即dp[k][j-1]加上数组在k到i之间的元素之和。
   • 计算dp[i][j]的过程中，需要更新当前的最小和minSum，如果dp[i][j]等于total/j，说明当前的分组和可以满足题目要求，将minSum更新为total/j，并继续遍历。
5. 最后输出minSum即为最小的和。

下面是使用动态规划实现的代码：

#include<iostream>
using namespace std;

int main()
{
    int n,a[1000002];
    cin>>n;
    int total = 0;
    for(int i=1;i<=n;i++)    //输入 
    {
        cin>>a[i];
        total += a[i];
    }
    int minSum = INT_MAX;
    int dp[1000002][1000002];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j] = INT_MAX;
        }
    }
    dp[0][0]=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            dp[i][j] = INT_MAX;
            for(int k=j-1; k<i; k++){
                dp[i][j] = min(dp[i][j], dp[k][j-1]+total/i);
            }
            if(dp[i][j]==total/i){
                minSum = min(minSum, dp[i][j]);
            }
        }
    }
    cout<<minSum;
    return 0;
}

希望我的回答对你有所帮助！如有疑问，请继续追问。