MENU

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

2018 年 12 月 15 日 • 阅读: 2030 • 练习阅读设置

[编程题] 有趣的数字

  • 时间限制: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日 星期六
最后编辑于: 2019 年 01 月 26 日