挑战程序设计竞赛
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)
下面解法的可取之处
- 使用预处理，从文件读入读出数据
- 使用插入器将从输入流读取的数据插入到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;
}
