CodeForces - 667B

题目链接：https://codeforces.com/problemset/problem/667/B

As some of you know, cubism is a trend in art, where the problem of constructing volumetrical shape on a plane with a combination of three-dimensional geometric shapes comes to the fore.

A famous sculptor Cicasso, whose self-portrait you can contemplate, hates cubism. He is more impressed by the idea to transmit two-dimensional objects through three-dimensional objects by using his magnificent sculptures. And his new project is connected with this. Cicasso wants to make a coat for the haters of anticubism. To do this, he wants to create a sculpture depicting a well-known geometric primitive — convex polygon.

Cicasso prepared for this a few blanks, which are rods with integer lengths, and now he wants to bring them together. The i-th rod is a segment of length li.

The sculptor plans to make a convex polygon with a nonzero area, using all rods he has as its sides. Each rod should be used as a side to its full length. It is forbidden to cut, break or bend rods. However, two sides may form a straight angle .

Cicasso knows that it is impossible to make a convex polygon with a nonzero area out of the rods with the lengths which he had chosen. Cicasso does not want to leave the unused rods, so the sculptor decides to make another rod-blank with an integer length so that his problem is solvable. Of course, he wants to make it as short as possible, because the materials are expensive, and it is improper deed to spend money for nothing.

Help sculptor!

Input
The first line contains an integer n (3 ≤ n ≤ 105) — a number of rod-blanks.

The second line contains n integers li (1 ≤ li ≤ 109) — lengths of rods, which Cicasso already has. It is guaranteed that it is impossible to make a polygon with n vertices and nonzero area using the rods Cicasso already has.

Output
Print the only integer z — the minimum length of the rod, so that after adding it it can be possible to construct convex polygon with (n + 1) vertices and nonzero area from all of the rods.

Examples
Input
3
1 2 1
Output
1
Input
5
20 4 3 2 1
Output
11
Note
In the first example triangle with sides {1 + 1 = 2, 2, 1} can be formed from a set of lengths {1, 1, 1, 2}.

In the second example you can make a triangle with lengths {20, 11, 4 + 3 + 2 + 1 = 10}.

毕加索为此准备了一些空白，这是一个整数长度的杆，现在他想将它们组合在一起。第i个杆是长度为li的段。

雕刻家计划用一个非零区域制作一个凸多边形，使用他所有的杆作为它的侧面。每根杆应该用作其全长的一侧。禁止切割，折断或弯曲杆。但是，两侧可以形成直角。

Cicasso知道不可能用他选择的长度从杆中制造出具有非零区域的凸多边形。毕加索不想留下未使用的杆，因此雕塑家决定制作一个整数长度的杆坯，以便他的问题可以解决。当然，他希望尽可能缩短它，因为这些材料价格昂贵，而且花钱无所事事是不恰当的。

帮助雕刻家！

输入
第一行包含一个整数n（3≤n≤105） - 一些棒状空白。

第二行包含n个整数li（1≤li≤109） - 棒的长度，Cicasso已经拥有。保证使用Cicasso已经具有的杆制作具有n个顶点和非零区域的多边形是不可能的。

产量
打印唯一的整数z - 杆的最小长度，以便在添加它之后，可以构造具有（n + 1）个顶点的凸多边形和来自所有杆的非零区域。

解题思路：一共有三种情况，每一次都找出它的最大的长度，第一种就是，这个最大的长度小于剩下的长度的和，这时候就是最大的长度减去剩下长度的和再加1；
第二种就是它们相等，那么是输出1；
第三种最大的长度小于它的和时，就需要找出一个最小的和次小的数，然后找一个最小的长度加一个长度能够大于次小的长度，那么就输出这个长度；

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include<queue>
#include <math.h>
#include <string.h>
#define ll long long
#define pi 3.14159265358979
using namespace std;
const int MAXN=500000;
int b[MAXN],c[MAXN];
int INF=99999999;
int main()
{
    int a;
    cin>>a;
    int falg=1;
     int minn=INF;
    int maxx=0,sum=0;
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    for(int i=1;i<=a;i++)//输入和找最大长度；
    {
        cin>>b[i];
        if(b[i]>maxx)
            maxx=b[i];
    }
    for(int i=1;i<=a;i++)//求和
    {
        if(b[i]!=maxx)
            sum+=b[i];
    }
    if(sum<maxx)//第一种情况
    {
       cout<<maxx-sum+1;
    }
    else if(sum==maxx)
    {
        cout<<"1";
    }
    else if(sum>maxx)//第二种情况
    {
        for(int i=1;i<=a;i++)
        {
            c[b[i]]++;
            if(b[i]<minn)
                minn=b[i];
        }
        int ss=minn;
        int sss=INF;
        for(int i=1;i<=a;i++)//第三种情况
        {
            if(b[i]!=ss)
            if(b[i]<sss)
            {
                sss=b[i];
            }
        }
        for(int i=1;i<=a;i++)
        {
            if(ss+i>sss)
            {
                cout<<i;
                break;
            }
        }
    }
    return 0;
}