[2016-05-01][codeforces][667B - Coat of Anticubism]

• 时间:2016-05-01 14:13:45 星期日

• 题目编号:[2016-05-01][codeforces][667B - Coat of Anticubism]

• 题目大意:给定n条边,问至少要增加一条多长的边才能使得这些边能组成一个凸多边形,保证n条边一定不能组成凸多边形,

• 分析:

  • 增加一条边,使得这些边能组成三角形,这条边的最小值就是答案
  • 假设增加一条边之和,组成的不是三角形,假设是4边行,那么可以把某两条边缩短,使得某相邻的两条边变成一条边,进而使得4边形变成3角形,故不是三角形的情况一定还能把边缩短,所以三角形的情况才是最优的情况

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1E5 + 10;
int main(){
        int n,a,b,tmp;
        a = b = 0;
        scanf("%d",&n);
        for(int i = 0 ; i < n ; ++i){
                scanf("%d",&tmp);
                if(tmp > a){
                        b += a;
                        a = tmp;
                }else b += tmp;               
        }
        int ans = a - b + 1;
        printf("%d\n",ans);
        return 0;
}

[2016-05-01][codeforces][667B - Coat of Anticubism]

原文：http://www.cnblogs.com/qhy285571052/p/259752a20c81eee15fa2d53539f6a06a.html