「2021年TYWZ普及模拟题」多边形 待定题解

题目描述

一个凸多边形具有非常多优秀的性质，它的任意内角小于或等于 $180^{。}$ 。

小 F 将 $n$ 条边交给小 Y， 询问小Y这 $n$ 条边能否围成一个凸 $n$ 边形，小 Y 当然知道这道题的答案，但是她决定用这个问题考考你。

输入格式

输入文件的第一行，包含一个正整数 $T$，表示有 $T$ 组测试数据，每组数据包含两行。

每组数据的第一行包含一个正整数 $n$，表示给定 $n$ 条边。

每组数据的第二行包含 $n$ 个正整数 $a_1{a}_2\dots$ $\dots a_n$，以空格隔开，表示 $n$ 条边的长度。

输出格式

输出 $T$ 行，每行输出YES或NO，输出YES表示可以围成一个凸多边形，输出NO表示不可以围成一个凸多边形。

样例

样例输入 1

2
3
3 4 5
3
2 7 3
1
2
3
4
5

样例输出 1

YES
NO
1
2

样例输入 2

2
4
1 2 3 4
4
8 2 3 3
1
2
3
4
5

样例输出 2

YES
NO
1
2

数据范围与提示

样例 $1$ 说明：

第一组数据中的三条边显然可以构成一个直角三角形，因为 $3\times 3+4\times 4=5\times 5$。

第二组数据中的三条边无法构成一个三角形，应为三角形的任意两条边之和大于第三边，而 $2+3<7$。

思路与部分实现

直接考虑用最长边的长度小于其余边长度之和为凸多边形的定义 $\text{AC}$ 此题。 代码实现如下：

int n,x,maxn=-1,sum=0;
scanf("%d",&n);
while(n--){
	scanf("%d",&x);
	maxn=max(maxn,x),sum+=x;
}
if(sum-maxn>maxn)
	printf("YES\n");
else printf("NO\n");
1
2
3
4
5
6
7
8
9

完整代码

#include
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n,x,maxn=-1,sum=0;
        scanf("%d",&n);
        while(n--){
            scanf("%d",&x);
            maxn=max(maxn,x),sum+=x;
        }
        if(sum-maxn>maxn)
        	printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

文章小结