兩兩配對內插補點最小 C++解法

題目描述

給定一個長度為偶數的數組arr，将該數組中的數字兩兩配對并求和，在這些和中選出最大和最小值，請問該如何兩兩配對，才能讓最大值和最小值的內插補點最小？

輸入描述:

一共2行輸入。

第一行為一個整數n，2<=n<=10000, 第二行為n個數，組成目标數組，每個數大于等于2，小于等于100。

輸出描述:

輸出最小的內插補點。

示例1

輸入

4

2 6 4 3

輸出

1

示例2

輸入

6

11 4 3 5 7 1

輸出

3

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>

using namespace std;


void main()
{
	int n;
	cin >> n;
	int* num = new int[n];
	for (int i = 0;i < n;i++)
		cin >> num[i];
	sort(num, num + n);
	int mi = INT_MAX, ma = 0, i = 0, j = n - 1;
	while (i < j)
	{
		int sum = num[i] + num[j];
		mi = min(mi, sum);
		ma = max(ma, sum);
		i++;
		j--;
	}
	cout << ma - mi << endl;
}
           

思路：将整個數組排序，之後第一個元素與最後一個元素比較，第二個元素與倒數第二個元素比較，以此類推，将接受到的最大值和最小值儲存起來，進行減法。先排序後組合的原因是這樣每組資料的浮動不會太大，總體都比較接近。