#include <cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int arr[50000001];
int main()
{
int T;
scanf("%d",&T);
while (T--){
int n, flag = 0;
cin>>n;
for (int i=0;i<n;i++)
cin>>arr[i];
sort(arr,arr+n);
for (int i=0;i<n-2;i++){
if (arr[i]+arr[i+1]>arr[i+2]){
flag=1;
break;
}
if (i>45)
break;
}
if (flag==1)
puts("YES");
else if (flag==0)
puts("NO");
}
return 0;
}

我知道陣列好像太大了,但也不能再小了

請大大們幫忙

這題其實可以不必將所有邊長儲存起來的~

你可以先嘗試構造出無法組成三角形的N條邊長(越小越好),

EX:
　3邊: 1 1 2　(無法組成三角形)
　4邊: 1 1 2 3　(無法組成三角形)
　5邊: ...
　6邊: ...

你會發現有著某種規律(其實就是某個很著名的數列),
由於該數列成長很快,
所以在邊長最長是 10^9 之下,
其實只要N大於某個特定的值(不會很大)之後就能確定一定能組成三角形,
若N小於等於該特定值就直接O(N^3)窮舉驗證即可~

以上提供你參考~
希望有幫助到你~ OwO

NA71%......
是我有誤解您的想法嗎?

#include<algorithm>

using namespace std;

int arr[46];

int input(){

char cha;

int x = 0;

while (cha=getchar())

if (cha!=' '&&cha!='\n')

break;

x=cha-'0';

while(cha = getchar()){

if (cha==' '||cha=='\n')

break;

else

x=x*10+(cha-'0');

}

return x;

}

int main()

{

int T;

scanf("%d",&T);

while (T--)

{

int n, flag = 0;

n=input();

if(n>45)puts("YES");

else{

for (int i = 0; i < n; i++)

arr[i] = input();

sort(arr, arr+n);

for (int i = 0; i < n-2; i++)

{

if (arr[i] + arr[i+1] > arr[i+2])

{

flag = 1;

break;

}

}

if (flag == 1)

puts("YES");

else if (flag == 0)

puts("NO");

}

}

return 0;

}

沒錯呀~
方法是對的唷~

只是別忘了當 n>45 時還是要輸入邊長,
只是不用儲存起來而已~

感謝!已AC!

不好意思，借討論串問一下最後一筆測資導致的 TLE 問題

我也是自己寫 getchar() 讀取，個數如果小於等於 45 個時需要紀錄就呼叫 scanInt 不然就是呼叫 scanTrash 

但是最後一筆測資都是 TLE，難道是我寫的 scanTrash 兩個判斷太花時間嗎...?

inline void scanInt(int &x){

  char c;

  while((c=getchar())==' ' or c=='\n');

  for(x=c-'0';(c=getchar())>='0' and c<='9';x=10*x+c-'0');

}

inline void scanTrash(char c=' '){

  while((c=getchar())==' ');

  while((c=getchar())>='0');

}

如果要使用 cin.ignore(1e9,'\n')，則會導致第4筆測資 TLE

 應該是 cin/cout 溝通的問題，

這題使用 cin.ignore(1e9, '\n') 要記得優化 cin 、 cout ，參見這篇。

至於執行速度的差別起因，本人見識短淺，無法回答。但推測是 C++ 底下實作時，有直接調用到硬體和一些組合語言來進行優化和加速。

提供我的作法給您參考

我是先將整個測資掃一遍 ( not clean buffer ) 紀錄所有的換行位置，

遇到 n > 45 時，直接跳過整段。