题解 CF6A 【Triangle】

Heartlessly · 2018-02-15 16:09:40 · 题解

算法介绍

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

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

• 从四根木棍中挑出三根显然只有 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;
}