题目描述:输入n个数,以回车结束输入,把这些数分成两组,使得两组的差值c(c>=0)最小,输出这个差值

输入示例1

3 2 6

输出示例1

1

输入示例2

4 6 7 9

输出示例2

0

思路:前缀和

设第一组的数之和为x,第二组数之和为y,所有数之和为sum

则有 x+y=sum

设c为最小的差值,则c=|x-y|,设x>=y,则c=x-y

则联立两个式子可得 c=sum-2*y

则通过前缀和遍历获取y的值,并求出最小值

前缀和:

设数组sum是数组a的前缀和,即sum[i]为a[0]加到a[i-1]的和,且sum[0]=0,sum和a的下标都从1开始。

则有a[l]+…+a[r]=sum[r]-sum[l-1];

#include<iostream>
#include<numeric>
#include<sstream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    ////读入数据流中的数字
    vector<int> vec(1);
    string a;
    getline(cin, a);
    istringstream i(a);
    string s;
    while (i >> s)
    {
        vec.push_back(stoi(s));
    }
	//////

    int sum = accumulate(vec.begin(), vec.end(), 0);	
    int minv = INT_MAX, n = 0;

    vector<int> sumvec(vec.size() + 1);
    ///////////构造前缀和
    int d = 0;
    sumvec[0] = 0;
    for (int i = 1; i < vec.size(); i++)
    {
        d += vec[i];
        sumvec[i] = d;
    }
	/////////////////
    
    ///////////////遍历前缀和获取最小差值   
    for (int i = 0; i < sumvec.size(); i++)
    {
        for (int j = 1; j < sumvec.size(); j++)
        {
            for (int k = 0; k < j; k++)
            {
                int x = sumvec[j] - sumvec[k];
                minv = min(minv, abs(sum - 2 * x));
            }
        }
    }
    cout << minv;
}

Q.E.D.