codeforces 667B B. Coat of Anticubism(水题)
题目链接:
1 second
256 megabytes
standard input
standard output
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!
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.
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.
3
1 2 1
1
5
20 4 3 2 1
11
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}.
题意:
给出这些不能形成凸多边形的边,问至少加多长才能形成凸多边形;
思路:
不能形成凸多边形说明最长的那条边太长,所以把除了最长边的其它边加在一起再加上答案使其比最长边大一就行;
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+;
const int N=1e5+;
const int inf=0x3f3f3f3f;
const double PI=acos(-1.0);
int a[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+,a+n+);
LL sum=;
for(int i=;i<n;i++)
{
sum+=(LL)a[i];
}
cout<<a[n]-sum+<<"\n";
// printf("%I64d\n",a[n]-sum+1); return ;
}
最新文章
- vim的一些配置
- windows下安装swoole。
- p2p穿透技术
- 基于C#的SolidWorks插件开发(2)--创建插件
- SQL Server 系统时间
- KEIL段协定
- 2016";百度之星"; - 资格赛(Astar Round1) 1004
- CSS3学习笔记(1)-CSS3选择器
- backtracking问题
- js 过多 导致页面加载过慢
- 非root用户ssh 执行 sudo远程机器免密钥
- bzo1606: [Usaco2008 Dec]Hay For Sale 购买干草
- 20175314 《Java程序设计》第三周学习总结
- 【Alpha版本】冲刺阶段——Day2
- rocketmq安装与基本操作
- Flink 的广播变量
- curl 知识点
- CodeDom生成类文件
- oracle 日期函数 求年的最后一天、第一天,月的最后一天
- as3中xml文件的加载和读取
热门文章
- T3138 栈练习2 codevs
- CODEVS_2800 送外卖 状态压缩+动态规划
- Maven自动部署(SCM-SVN/Git)(maven-scm-plugin/maven-release-plugin插件的使用)
- transition、animation在macbook air上图片动画边缘抖动2
- Java 读写文件大全
- How to Install a Language Pack
- paramiko使用exec_command执行rm -rf删除目录的坑
- 在windows中增加linux命令
- linux 环境 php 链接 sqlserver 2008
- 手机号码归属地查询免费api接口代码