MENU

HUNNU11788 Ole-Johan Dahl and Kristen Nygaard(二分)

2018 年 06 月 12 日 • 阅读: 1472 • 练习阅读设置

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

3

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 星期二
最后编辑于: 2018 年 07 月 11 日