#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
這題其實可以不必將所有邊長儲存起來的~
你可以先嘗試構造出無法組成三角形的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;
}
不好意思,借討論串問一下最後一筆測資導致的 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 溝通的問題,
不好意思,借討論串問一下最後一筆測資導致的 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++ 底下實作時,有直接調用到硬體和一些組合語言來進行優化和加速。