codeforces - 766B【三角形判斷】

題解By: Jstyle
知識(shí)點(diǎn)一
?? ?要想三邊滿足構(gòu)成三角形的條件有兩個(gè)
?? ?1、任意兩邊之和大于第三邊。
?? ?2、任意兩邊之差小于第三邊。
知識(shí)點(diǎn)二
?? ?假設(shè)三邊為 a, b, c 且滿足 a <= b <= c;那么只需要滿足 a+b > c即可;
?? ?證明：
?? ?任意兩邊之和大于第三邊：
?? ?因?yàn)?a <= b <= c, 則 a+c > b && b+c > a 是顯然的;
?? ?任意兩邊只差小于第三邊：
?? ?因?yàn)? a+b > c 所以: a > c-a && b < c-a;
?? ?那么我們只需要證明 b-a < c即可;
?? ?因?yàn)? b < c 所以 b-a < c-a < c即 b-a < c;
?? ?證畢。

此題解法：
?? ?有了以上假設(shè)解決這道題會(huì)非常容易。
?? ?這道題有個(gè)很樸素的做法就是我們?nèi)ト豧or循環(huán)枚舉三條邊是否滿足條件，但是超時(shí)也是顯然的。
?? ?基于知識(shí)點(diǎn)二我們可以有如下做法：
?? ?1、將給定的n條邊進(jìn)行排序;
?? ?2、從大到小去判斷相鄰的三條邊是否有 a[i] < a[i-1]+a[i-2]的關(guān)系;
?? ?3、如果有就直接跳出循環(huán)并輸出"YES";否則繼續(xù)去執(zhí)行2;
?? ?這樣我們只需要 (排序+一層循環(huán)遍歷) 就可以解決了,時(shí)間復(fù)雜度 O(n*logn);
?? ?
解法的合理性：
?? ?我們來(lái)證明一下這樣的可行性：
?? ?1、對(duì)于從大到小遍歷的 c 來(lái)言，要想找到兩個(gè)數(shù) a+b > c,肯定a,b越大才越有可能成立。
?? ?2、那對(duì)于我們排序過(guò)后的數(shù)組而言，肯定是c往下相鄰的兩個(gè)數(shù)是最大的。即就是a[i-1],a[i-2];
?? ?3、如果對(duì)于當(dāng)前的 a[i-2]+a[i-2] <= a[i];那么a[i]這條邊就可以從我們的遍歷數(shù)組中去掉了，
?? ??? 因?yàn)楸萢[i]小的最大的兩條邊都不滿足 a+b > c了，那么更小的邊更不會(huì)滿足，因此我們把a(bǔ)[i-1]繼續(xù)作為
?? ??? c這條邊繼續(xù)判斷。
?? ?? ?
希望大家能從這道理得到一些思考和啟發(fā)，此題代碼不長(zhǎng)，但是需要基礎(chǔ)的思維。

代碼：

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

?

posted on 2017-02-11 10:24 NWU_ACM 閱讀(...) 評(píng)論(...) 編輯 收藏

轉(zhuǎn)載于:https://www.cnblogs.com/NWUACM/p/6388734.html

總結(jié)

以上是生活随笔為你收集整理的codeforces - 766B【三角形判断】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。