腾讯2017暑期实习生编程题C 有趣的数字（暴力）

[编程题] 有趣的数字

• 时间限制：1秒
• 空间限制：32768K

小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，相差最小的有多少对呢？相差最大呢？

输入描述:

 输入包含多组测试数据。
 对于每组测试数据：
 N - 本组测试数据有n个数
 a1,a2...an - 需要计算的数据
 保证:1<=N<=100000,0<=ai<=INT_MAX.

输出描述:

对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。

输入例子1:

6
45 12 45 32 5 6

输出例子1:

1 2

链接

传送门

题意

题面描述已经够清楚了。

题解

首先我们对数组进行排序。

最大差值肯定是数组两端元素的差，统计一下最大数的数量cnt1和最小数的数量cnt2那么答案为cnt1*cnt2。

最小差值为相邻元素的差，循环一遍求出，当最小差值为0时，需要统计所有相等元素的对数；最小差值大于0时，找有多少对相邻元素的差等于最小差值即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 100010;

int n;
int a[maxn];

void solve()
{
    sort(a, a + n);
    int pta = 0, ptb = n - 1;
    int suma = 1, sumb = 1;
    int ans1 = 0, ans2 = 0;
    while (pta < n && a[pta] == a[++pta]) // 最大差值处理
        suma++;
    while (ptb >= 0 && a[ptb] == a[--ptb])
        sumb++;
    ans1 = suma * sumb;
    int minnum = inf, tmp;
    for (int i = n - 1; i > 0; --i) // 最小差值处理
    {
        tmp = a[i] - a[i - 1];
        if (tmp < minnum)
            minnum = tmp;
    }
    if (minnum > 0) // 大于0时找等于minnum
    {
        for (int i = n - 1; i > 0; --i)
        {
           tmp = a[i] - a[i - 1];
            if (tmp == minnum)
                ans2++;
        }
    }
    else if (minnum == 0) // 等于0时找相等对数
    {
        for (int i = 0; i < n - 1; ++i)
        {
            pta = i;
            while (pta < n && a[i] == a[++pta])
                ans2++;
        }
    }
    printf("%d %d\n", ans2, ans1);
}

int main()
{
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        solve();
    }
    return 0;
}

The end.
2018年12月15日 星期六