放牧代码和思想
专注自然语言处理、机器学习算法

《挑战程序设计竞赛(第2版)》 1.6.1 三角形

目录

作为《挑战程序设计竞赛(第2版)》第一章最开始的“简单题”,直接三重循环遍历你就输了。给出一个O(nlogn)的算法,先排序O(nlogn),然后遍历至多n – 2次得出结果:

原题

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

       例如:

       输入:

              n= 5

              a= { 2, 3, 4, 5, 10}

       输出:

              12(选择3,4,5时)

      

       输入:

              n= 4

              a= {4, 5, 10, 20}

       输出:

              0(无论怎么选都无法组成三角形)

我的解法:

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;

///////////////////////////SubMain//////////////////////////////////
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;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 《挑战程序设计竞赛(第2版)》 1.6.1 三角形

分享到:更多 ()

评论 6

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    排序一下,从最大的三个数字开始,若可以组成三角形则为答案,否则舍弃最大的数字重复上述操作

    wet2_cn4年前 (2014-01-24)回复
    • 总结得对

      hankcs4年前 (2014-01-24)回复
      • C++新手求解用vector相对用数组直接排序有何优势?

        wet2_cn4年前 (2014-01-26)回复
        • 用STL的容器和算法简洁,容易拓展,而且有些STL的sort实现版本会依据元素的不同自动选取最佳的排序算法

          hankcs4年前 (2014-01-26)回复
          • 请问有什么STL的书推荐吗!!

            wet2_cn4年前 (2014-01-27)
          • 入门的话首推《C++标准程序库—自修教程与参考手册》

            hankcs4年前 (2014-01-27)

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机