首页 > 代码库 > codeforces - 766B【三角形判断】

codeforces - 766B【三角形判断】

题解By: Jstyle
知识点一
    要想三边满足构成三角形的条件有两个
    1、任意两边之和大于第三边。
    2、任意两边之差小于第三边。
知识点二
    假设三边为 a, b, c 且满足 a <= b <= c;那么只需要满足 a+b > c即可;
    证明:
    任意两边之和大于第三边:
    因为 a <= b <= c, 则 a+c > b && b+c > a 是显然的;
    任意两边只差小于第三边:
    因为: a+b > c 所以: a > c-a && b < c-a;
    那么我们只需要证明 b-a < c即可;
    因为: b < c 所以 b-a < c-a < c即 b-a < c;
    证毕。

此题解法:
    有了以上假设解决这道题会非常容易。
    这道题有个很朴素的做法就是我们去三重for循环枚举三条边是否满足条件,但是超时也是显然的。
    基于知识点二我们可以有如下做法:
    1、将给定的n条边进行排序;
    2、从大到小去判断相邻的三条边是否有 a[i] < a[i-1]+a[i-2]的关系;
    3、如果有就直接跳出循环并输出"YES";否则继续去执行2;
    这样我们只需要 (排序+一层循环遍历) 就可以解决了,时间复杂度 O(n*logn);
    
解法的合理性:
    我们来证明一下这样的可行性:
    1、对于从大到小遍历的 c 来言,要想找到两个数 a+b > c,肯定a,b越大才越有可能成立。
    2、那对于我们排序过后的数组而言,肯定是c往下相邻的两个数是最大的。即就是a[i-1],a[i-2];
    3、如果对于当前的 a[i-2]+a[i-2] <= a[i];那么a[i]这条边就可以从我们的遍历数组中去掉了,
       因为比a[i]小的最大的两条边都不满足 a+b > c了,那么更小的边更不会满足,因此我们把a[i-1]继续作为
       c这条边继续判断。
       
希望大家能从这道理得到一些思考和启发,此题代码不长,但是需要基础的思维。

代码:

技术分享
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #define N 100005
 5 using namespace std;
 6 
 7 int n, a[N];
 8 int main()
 9 {
10     while(scanf("%d", &n) != EOF){
11         for(int i = 1; i <= n; ++ i)    scanf("%d", &a[i]);
12         
13         sort(a+1, a+n+1);
14         int ok = 0;
15         for(int i = n; i >= 3; --i){
16             int x = a[i], y = a[i-1], z = a[i-2];
17             if(y+z > x){
18                 ok = 1;
19                 break;
20             }
21         }
22         printf(ok ? "YES\n" : "NO\n");
23     }
24     return 0;
25 }
View Code

 

codeforces - 766B【三角形判断】