挑戰(zhàn)程序設(shè)計競賽

標簽 ： acm
參考

P26

1.6 有n根棍子，棍子i的長度為ai，想要從中選出3根棍子組成周長盡可能長的三角形，請輸出最大的周長，若無法組成三角形則輸出0。

思路：直接三重循環(huán)遍歷能得到結(jié)果，時間復(fù)雜度為$O(n^3)$,如果給定的棍子是排好序的，那事情就好辦了，若
$n1<n2<n3<n4<...<nk$,選取鄰近的三個數(shù)即可。顯然如果選擇為ni,n(i+1),n(i+2)

#define ONLINE_JUDGE
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
 
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    vector<int> coll;
    copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(coll));
    sort(coll.begin(), coll.end(), greater<int>());
    //copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
    bool found = false;
    for (int i = 0; i < n - 2; ++i)
    {
        if (coll[i] < coll[i + 1] + coll[i + 2])
        {
            cout << coll[i] + coll[i + 1] + coll[i + 2] << endl;
            found = true;
            break;
        }
    }
    if (!found)
    {
        cout << 0 << endl;
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}