HUNNU11788 Ole-Johan Dahl and Kristen Nygaard（二分）

Ole-Johan Dahl and Kristen Nygaard

Time Limit: 3000ms
Memory Limit:32768KB
Total submit users: 8
Accepted users: 6

Problem description

class Shape{virtual double area();};
class Triangle : public Shape{double area(){...}};
balabala……

你可能在某本面向对象程序设计的教材中看过这个例子，或者，肯定看过类似的例子。这个例子是用来演示继承与多态的。面向对象程序设计是程序设计的一种范式，此处省略500字。公认最早的一款面向对象程序设计语言是Simula，由两个挪威人Ole-Johan Dahl和Kristen Nygaard开发。他们也被称作是Simula与OOP之父。因为这些贡献，他们于2001年获得ACM图灵奖（For ideas fundamental to the emergence of object-oriented programming, through their design of the programming languages Simula I and Simula 67）。你应该发现了，Simula其实是两门语言的统称——Simula I和Simula67。不过这不是重点。
说了这么多，看到那个Triangle类了吗？给定一个数组，一共有N个正整数，代表线段的长度，问能够构成三角形的三元组一共有多少个。三元组被认为是不同的，当且仅当三个长度在数组中的下标的组合不完全相同。

Input

输入由多个案例构成。每个案例由二行组成。第一行是一个正整数N。第二行是N个正整数。所有给定的数均不超过1000。
N为0表示输入结束。

Output

每个案例输出一行，为答案。

Sample Input

4
2 2 3 4
0

Sample Output

Judge Tips

提示：如果将这个数组记作A，则A中一共可以选出3个三元组构成三角形，分别是(A0,A1,A2)，(A0,A2,A3)和(A1,A2,A3)。

链接

http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11788

题意

题面讲了那么多，其实就是让你求在n个正整数中找能构成三角形的三元组数。

给定一个数组，一共有N个正整数，代表线段的长度，问能够构成三角形的三元组一共有多少个。三元组被认为是不同的，当且仅当三个长度在数组中的下标的组合不完全相同。

题解

首先，暴力三重循环当然是不可取的，时间复杂度$O(n^3)$，n达到了1000。

然后想着怎么降低时间复杂度呢...我们知道，构成三角形的条件是两边之和大于第三边，所以我们先对数组排个序，如果$a[i]+a[j] > a[k]$，我们可以找到k的一个边界值，那么在这个区间中的都符合条件。具体做法如下：

首先要将数组进行排序
排序后从数组的最右边的元素开始进行循环right，一个变量指针指向数组的第一个元素left，一个变量指针指向数组当前循环元素的前一个元素medium
如果满足nums[left] + nums [medium] > nums[right], 则说明在left到right中的所有元素都满足可以组成三角形的条件，所以将能够组成三角形的个数增加medium - left个
如果不满足上述式子，则将left向前移动

代码

1112KB
203ms
868B

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int a[maxn];

int main()
{
    int n;
    while (scanf("%d", &n))
    {
        if (n == 0)
            break;
        int ans = 0;
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        sort(a, a + n);
        for (int r = n - 1; r >= 2; --r)
        {
            int l = 0, mid = r - 1;
            while (l < mid)
            {
                if (a[l] + a[mid] > a[r])
                {
                    ans += mid - l;
                    mid--;
                }
                else
                    l++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

比赛的时候没写出来，还是太菜了阿。这道题貌似是LeetCode原题，赛后也是参考了别人的题解。

The end.
2018-06-12 星期二