Heartlessly 的博客

题解 CF6A 【Triangle】

算法介绍

  • 据说这道题的正解是暴力枚举什么的,但是蒟蒻在这里给大家介绍另一种贪心的解法。

  • 先把四根木棍的长度按从小到大排序。

  • 从四根木棍中挑出三根显然只有 4 种方法(如下)

    1. 1 2 3
    2. 1 2 4
    3. 1 3 4
    4. 2 3 4
  • 排列组合就是: $C_{4}^{3}= \frac{4!}{\left ( 4-3 \right )!3!}= \frac{4\times 3\times 2\times 1}{3\times 2\times 1}= 4$

  • 其中有 2 种不需要考虑,原因如下:

  • 如果第一根木棍和第二根木棍的总长大于第四根,那么就一定大于第三根,所以只要判断第一根木棍和第二根木棍的总长第三根的关系。

  • 同理,如果第一根木棍和第三根木棍的总长大于第四根,那么第二根木棍和第三根木棍的总长也一定大于第四根,所以只要判断第二根木棍和第三根木棍的总长第四根的关系。

  • 也就是说,2,3 两种挑法可以忽略,退化的三角形也一样判断。

  • 通过以上思路,并不难写出代码。

示例代码

#include <bits/stdc++.h>
using namespace std;
int f[5];//数组存比较方便排序
int main(){
    for ( int i = 1; i <= 4; i++ )
    scanf ( "%d", &f[i] );
    sort ( f + 1, f + 5 );//快速排序
    if ( f[1] + f[2] > f[3] || f[2] + f[3] > f[4] ) printf ( "TRIANGLE\n" );
    else if ( f[1] + f[2] == f[3] || f[2] + f[3] == f[4] ) printf ( "SEGMENT\n" );
    else printf ( "IMPOSSIBLE\n" );
    return 0;
} 

2018-02-15 16:09:40 in 题解