时间限制: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

思路:先排序。

最大差的对数:分别统计最大数个数与最小数个数,然后相乘即可。

最小差的对数:要考虑是否有差为0的情况,如果没有,for遍历一次即可统计(不会出现排列组合问题)。如果有,则用map统计每个数的个数,最后在处理。举例:1 1 1 2 2 2 3,最小对数为3 + 3=6,如果直接统计,结果是4.

代码:

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main()
{
    int n, *a;
    while(cin >> n)
    {
        map<int, int> M;
        a = new int[n];
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
            M[a[i]]++;
        }
        if(n == 1)
        {
            cout << "0 0" << endl;
            delete[] a;
            continue;
        }
        sort(a, a+n);
        // 处理数字全部一样的情况
        if(a[0] == a[n-1])
        {
            int t = (n*(n-1))/2;
            cout << t << " " << t << endl;
            continue;
        }
        int minx = 1, miny = 1;
        for(int i = 1; a[i] == a[0] && i < n; i++)
            minx++;
        for(int i = n-2; a[i] == a[n-1] && i >= 0; i--)
            miny++;
        int mins = a[1] - a[0], min_cnt = 1;
        for(int i = 2; i < n; i++)
        {
            if(a[i] - a[i-1] < mins)
            {
                mins = a[i] - a[i-1];
                min_cnt = 1;
            }
            else if(a[i] - a[i-1] == mins)
            {
                min_cnt ++;
            }
        }
        if(mins == 0)
        {
            min_cnt = 0;
            map<int, int>::iterator iter;
            iter = M.begin();
            while(iter != M.end()) {
                min_cnt += (iter->second * (iter->second-1))/2;
                iter++;
            }
        }
        cout << min_cnt << " " << minx*miny << endl;
        delete[] a;
    }
    return 0;
}


你可能感兴趣的文章

评论区

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

您好,欢迎到访网站!
  查看权限

«   2019年3月   »
123
45678910
11121314151617
18192021222324
25262728293031