牛客周赛 Round 56 D 构造故事

题目大意

给定若干根木棍长度，要求从中选出 3 根组成一个三角形，并使三角形周长最大；若无法组成任何三角形则输出 -1。

25pts，暴力dfs，TLE

#include <iostream>
#include <vector>
using namespace std;
const int maxn=1e4+10;
long long int T,n,aa[maxn],ans;
bool vis[maxn];

long long int summ(vector<int> tri,int c) {
    int a=tri[0],b=tri[1];
    if(a+b<=c) {
        return -1;
    }else if(a+c<=b) {
        return -1;
    }else if(b+c<=a) {
        return -1;
    }
    return a+b+c;
}

void dfs(int y,vector<int>triangle) {
    for(int i=0;i<n;i++) {
        if(!vis[i]) {
            if(y+1==3) {
                //cout<<triangle[0]<<" "<<triangle[1]<<" "<<aa[i]<<endl;
                ans=max(ans,summ(triangle,aa[i]));
                continue;
            }
            triangle.push_back(aa[i]);vis[i]=true;
            dfs(y+1,triangle);
            triangle.pop_back();vis[i]=false;
        }
    }
}

int main()
{
    cin>>T;
    while (T--) {
        fill(begin(aa),end(aa),0);
        fill(begin(vis),end(vis),false);
        ans=-1;
        cin>>n;
        for(int i=0;i<n;i++) {
            cin>>aa[i];
        }
        dfs(0,{});
        cout<<ans<<endl;
    }
    return 0;
}

参考的题解思路

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e4+7;
const ll maxLen=static_cast<ll>(1e18)+7;
ll len[maxn],n,t,ans;
int main() {
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        for(int i=1;i<=n;i++) {
            cin>>len[i];
        }
        ans=0;
        sort(&len[1],&len[n+1],less<int>());
        for(int i=n;i>=3;i--) {
            for(int j=i-1;j>=2;j--) {
                if(len[j-1]+len[j]<=len[i])  // 别写反了，这是不满足条件的情况
                    break;
                ans=max(ans,len[j-1]+len[j]+len[i]);  // 如果这个不能，那继续往下枚举也没有意义，因为次大+次次大<大边
                break;
            }
        }
        if(ans==0) {
            cout<<-1<<endl;
        }else {
            cout<<ans<<endl;
        }
    }
}
//AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71774749