题目描述: 有n根棍子，棍子的长度为a，想要从中选出3根棍子组成周长尽可能长的三角形 约束条件: 3<= n <= 100 1 <= ai <= 10^6
思路：
组成三角形的充要条件：最长边长<另外两边长之和
（1）直接枚举：O(n^3)
#include <iostream> #include<algorithm> using namespace std; int main() { int n,a[105]; while(cin>>n){ for(int i=0;i<n;i++){ cin>>a[i]; } int ans=0; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ for(int k=j+1;k<n;k++){ int t=(a[i]-a[j]?a[i]-a[j]:a[j]-a[i]); if((a[i]+a[j]>a[k])&&t<a[k]) ans=max(ans,a[i]+a[j]+a[k]); } } } cout<<ans<<endl; } return 0; } （2）先排序再找规律if(a[i-2]+a[i-1]<a[i]) --i; else ans=a[i-2]+ai-1]+a[i];O(n log n) #include <iostream> #include<algorithm> using namespace std; int main() { int n,a[105]; while(cin>>n){ for(int i=0;i<n;i++){ cin>>a[i]; } int ans=0; sort(a,a+n); for(int i=n-1;i>=2;--i){ if(a[i]<a[i-1]+a[i-2]){ ans=a[i]+a[i-1]+a[i-2]; break; } } cout<<ans<<endl; } return 0; }