ACM模版

描述

题解

将前n项和求出来并排序，然后比较相邻两项其位置关系，如果可以组成序列，则说明其可能是所要求结果，然后从所有可能是结果的结果中取出最小值即可。
如：

序列 4 -1 5 -2 -1 2 6 -2

排序前

sum 4 3 8 6 5 7 13 11
pos 1 2 3 4 5 6 7 8

排序后

sum 3 4 5 6 7 8 11 13
pos 2 1 5 4 6 3 8 7

如果ABC为排序后的结果，那么当A和B不能组成序列，而A和C可以组成序列时，那么B和C一定可以组成序列，并且BC一定会比AC更优。

代码

#include <iostream>
#include <algorithm>

using namespace std;

int n;
struct node
{
    long long sum;
    int pos;
} Node[50005];

bool cmp(node &a, node &b)
{
    if (a.sum == b.sum)  // 此处不可省，要尽量保证可能出现的序列
    {
        return a.pos > b.pos;
    }
    return a.sum < b.sum;
}

int main()
{

    int i, flag;
    long long sum = 0, temp, res = 0;
    scanf("%d", &n);

    Node[0].pos = 0;
    Node[0].sum = 0;

    for (i = 1; i <= n; i++)
    {
        scanf("%lld", &temp);
        sum += temp;

        Node[i].pos = i;
        Node[i].sum = sum;
    }
    sort(Node, Node + n + 1, cmp);

    flag = 0;
    for (i = 1; i <= n; i++)
    {
        if (Node[i].pos - Node[i - 1].pos > 0 && Node[i].sum - Node[i - 1].sum > 0)
        {
            if (flag == 0)
            {
                flag = 1;
                res = Node[i].sum - Node[i - 1].sum;
            }
            else
            {
                if (Node[i].sum - Node[i - 1].sum < res)
                {
                    res = Node[i].sum - Node[i - 1].sum;
                }
            }
        }
    }

    printf("%lld\n", res);

    return 0;
}