Massive Algorithms: 《挑战程序设计竞赛(第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时）

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;

}

Labels