挑战程序设计竞赛

2014-1-29

参考

P26

• 1.6 有n根棍子，棍子i的长度为ai，想要从中选出3根棍子组成周长尽可能长的三角形，请输出最大的周长，若无法组成三角形则输出0。

思路：直接三重循环遍历能得到结果，时间复杂度为$O(n^3)$,如果给定的棍子是排好序的，那事情就好办了，若
n1<n2<n3<n4<...<nk,选取邻近的三个数即可。显然如果选择为ni,n(i+1),n(i+2)

下面解法的可取之处

1. 使用预处理，从文件读入读出数据
2. 使用插入器将从输入流读取的数据插入到coll 。
   copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(coll));

#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;
}