题目来源
小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,相差最小的有多少对呢?相差最大呢?
(虽然上厕所的时候不必想这么多但是我还是做了)
三种情况分别考虑
1 数字少于两个 输出为0 0
2 数字为两个 输出为1 1
3数字大于两个
首先考虑数字全为一样的情况,两者均为n*(n-1)/2
再考虑数字不完全一样的情况
最小差若为0,则将所有0的组合计数(需要考虑不相邻但同样的状态);若不为0,也计数(仅考虑相邻两个计数即可)。
最大差为最大值减去最小值,仅需分别计数a、b,并相乘即可
1对最小差为0时的计数一时无从下手,参考了牛客网上的解析后,发现可以按照穷举的方式将其挑出……
2利用vector实现而非基础数组形式,并使用sort实现排序。
vector相关输入方法
#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; }