本文主要是介绍【每日一题】腾讯2017暑期实习生编程题-3，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

• 题目
• 思路
• 相关思考
• 代码（C++/牛客）

题目

题目来源
小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，相差最小的有多少对呢？相差最大呢？
（虽然上厕所的时候不必想这么多但是我还是做了）

思路

三种情况分别考虑
1 数字少于两个 输出为0 0
2 数字为两个 输出为1 1
3数字大于两个
首先考虑数字全为一样的情况，两者均为n*（n-1）/2
再考虑数字不完全一样的情况
最小差若为0，则将所有0的组合计数（需要考虑不相邻但同样的状态）；若不为0，也计数（仅考虑相邻两个计数即可）。
最大差为最大值减去最小值，仅需分别计数a、b，并相乘即可

相关思考

1对最小差为0时的计数一时无从下手，参考了牛客网上的解析后，发现可以按照穷举的方式将其挑出……
2利用vector实现而非基础数组形式，并使用sort实现排序。
vector相关输入方法

代码（C++/牛客）

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n;
	while (cin >> n){
		if (n < 2){
			cout << 0 << ' ' << 0 << endl;
			continue;
		}
		if (n == 2){
			cout << 1 << ' ' << 1 << endl;
			continue;
		}
		//3个数以上的情况
		vector<int> data;
		while (n--){
			int temp;
			cin >> temp;
			data.push_back(temp);
		}
		int length = data.size();
		sort(data.begin(), data.end());
		//先求最小的，肯定是相邻的相减得到
		int min_val = abs(data[1] - data[0]);
		for (int i = 2; i < length; ++i){
			int cur = (data[i] - data[i - 1]);
			if (cur < min_val)
				min_val = cur;
		}
		//统计最小的数目
		int min_count = 0;
		if (min_val == 0){//有相同大小的数子，统计个数，用组合求对数
			for (int i = 1; i < length; ++i)
			{
				int j = i - 1;
				while (j >= 0 && data[i] == data[j]){
					++min_count;
					--j;
				}
			}
		}
		else
		{
			for (int i = 1; i < length; ++i){
				int cur = (data[i] - data[i - 1]);
				if (cur == min_val)
					++min_count;
			}
		}
		//求差最大的对数：最小的个数*最大的个数（如果最大的不等于最小的）
		int max_val = data[length - 1] - data[0];
		int max_count = 0;
		int a, b;
		a = b = 0;
		for (int i = 0; i < length; ++i){
			if (data[i] == data[0])
				++a;
		}
		for (int i = length - 1; i >= 0; --i){
			if (data[i] == data[length - 1])
				++b;
		}
		if (max_val == 0)//当最大等于最小，即数据全部一样eg. 1 1 1 1时，显然 4*4是不对的
			max_count = length*(length - 1) / 2;
		else
			max_count = a*b;

		cout << min_count << ' ' << max_count << endl;
	}
	return 0;
}

这篇关于【每日一题】腾讯2017暑期实习生编程题-3的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！