首页 > 试题广场 > 两两配对差值最小
[编程题]两两配对差值最小
  • 热度指数:7074 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个长度为偶数的数组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
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        Arrays.sort(a);
        
        int max=0,min=Integer.MAX_VALUE;
        for(int i=0,j=n-1;i<n/2;i++,j--){
            max=Math.max(max,a[i]+a[j]);
            min=Math.min(min,a[i]+a[j]);
        }
        System.out.println(max-min);
    }
}

发表于 2019-08-08 17:28:54 回复(3)
为什么这样就能保证差值最小呢?想严格证明一下,没有想出方法orz
发表于 2020-02-13 00:24:24 回复(1)
import sys
n=int(sys.stdin.readline().strip())
arr=list(map(int,sys.stdin.readline().strip().split()))
arr.sort()
plus=[]
for i in range(n//2):
    plus.append(arr[i]+arr[n-1-i])
print(max(plus)-min(plus))

发表于 2019-08-06 14:22:11 回复(0)
#include <iostream>
#include <algorithm> 
using namespace std;
int main()
{ 
    int num;
    cin >> num;
    int *data = new int[num];
    for (int i = 0; i < num; i++) {
        cin >> data[i];
    }
    sort(data, data + num);//对输入的数排序
    int *Sum = new int[num/2];
    for (int i = 0; i < num/2; i++) {
        Sum[i] = data[i] + data[num - 1 - i];//排序后两头的相加
    }
    sort(Sum, Sum + num / 2);//再排序,取最大和最小值
    int count=Sum[num/2-1]-Sum[0];
    cout << count;
    return 0;
}

发表于 2019-07-27 09:37:53 回复(0)
Python3行搞定  排序之后最大最小的配对 然后次大的和次小的配对  以此类推、
_, a = input(), sorted([int(x) for x in input().split(" ")])
b = [a[i] + a[-i-1] for i in range(int(len(a)/2))]
print(max(b) - min(b))


发表于 2019-12-05 11:27:14 回复(0)
贪心思想:如果让大的和大的配对,小的和小的配对,那么最大值和最小值的差距将会进一步拉大,因此尽可能让大的和小的配对,这样最大值和最小值的差距才会缩小,数对之和的分布也会尽可能平均。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strArr = br.readLine().trim().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        // 尽量让大小相近才能使得最大和最小值相差最小,因此只能大的和小的配对
        Arrays.sort(arr);
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length/2; i++){
            max = Math.max(arr[i] + arr[arr.length - 1 - i], max);
            min = Math.min(arr[i] + arr[arr.length - 1 - i], min);
        }
        System.out.println(max - min);
    }
}


编辑于 2021-01-31 22:13:27 回复(0)
package 两两配对差值最小;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

/*
 * 给定一个长度为偶数的数组arr,将该数组中的数字两两配对并求和,在这些和中选出最大和最小值。
 * 请问该如何两两配对,才能让最大值和最小值的差值最小?
 * 
 * 输入描述:
 * 一共2行输入。
 * 第一行为一个整数n,2<=n<=10000, 第二行为n个数,组成目标数组,每个数大于等于2,小于等于100。
 * 
 * 输出描述:
 * 输出最小的差值。
 * 
 * 输入例子1:
 * 4
 * 2 6 4 3
 * 
 * 输出例子1:
 * 1
 * 
 * 输入例子2:
 * 6
 * 11 4 3 5 7 1
 * 
 * 输出例子2:
 * 3
 */
/*
 * 算法:排序
 * 数据结构:双端队列
 * 思路:最大值与最小值配对,其次是次大值与次小值,以此类推,得到和的序列后,再取出最大的和和最小的和做减法
 * 先将数组进行从小到大排序,存入双端队列中,首尾值相加存入新数组中,双端队列同时去除首尾,循环直到队列中只有<=1个值
 * 和序列数组进行从小到大排序,将首尾相减
 */
public class Main {

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int arraySize = input.nextInt();
		int[] array = new int[arraySize];
		for (int i = 0; i < arraySize; i ++) {
			array[i] = input.nextInt();
		}
		input.close();

		Arrays.sort(array);
		Deque<Integer> deque = new ArrayDeque<Integer>();
		for (int i = 0; i < arraySize; i ++) {
			deque.add(array[i]);
		}
		
		int[] sum = new int[arraySize / 2];
		for (int i = 0; i < arraySize / 2 && deque.size() > 1; i ++) {
			sum[i] = deque.pollFirst() + deque.pollLast();
		}
		
		Arrays.sort(sum);
		System.out.println(sum[sum.length - 1] - sum[0]);
	}

}

发表于 2020-03-10 10:52:50 回复(0)

Java API解决
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    /**
     * 运行时间:101ms
     *
     * 占用内存:14180k
     * */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] record = new int[n];
        for (int i = 0; i < n; i++) {
            record[i]=scanner.nextInt();
        }
        Arrays.sort(record);

        int i=0;
        int j=n-1;
        while (j>i){
            record[i]=record[i]+record[j];
            i++;
            j--;
        }
        int[] add = new int[n / 2];
        System.arraycopy(record,0,add,0,n/2);
        Arrays.sort(add);
        System.out.println(add[n/2-1]-add[0]);
    }
}


发表于 2020-02-29 16:50:44 回复(0)
import java.util.Arrays;
import java.util.Scanner;

public class No3MinMax_Min {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr=new int[n];
        for (int i = 0; i <n ; i++) {
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);
        int max=arr[0]+arr[n-1];
        int min=max;
        for (int i = 1; i <n/2 ; i++) {
            if (arr[i]+arr[n-1-i]>max)
                max=arr[i]+arr[n-1-i];
            if (arr[i]+arr[n-1-i]<min)
                min=arr[i]+arr[n-1-i];
        }
        System.out.println(max-min);
    }
}

发表于 2020-02-21 10:29:57 回复(0)
O(n)的解法,桶排序
#include "bits/stdc++.h"
using namespace std;
int m[101]={};
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int v;cin>>v;
        m[v]++;
    }
    int l=0,r=100,mx=2,mn=200;
    while(l<=r){
        if(m[l]==0){
            l++;
            continue;
                 
        }
        if(m[r]==0){
            r--;
            continue;
        }
        int mm=min(m[l],m[r]);
        m[l]-=mm;if(l!=r)m[r]-=mm;
        mx=max(mx,r+l);
        mn=min(r+l,mn);
        //cout<<r<<" "<<l<<" "<<mx<<" "<<mn<<endl;
    }
    cout<<mx-mn;
}


发表于 2019-11-05 19:32:43 回复(0)
#include<bits/stdc++.h>
using namespace std;
// 贪心思想


int main() {
	int n;
	cin >> n;
	vector<int> f(n);
	for (int i=0; i<n; ++i) {
		cin >> f[i];
	}	
	sort(f.begin(), f.end());
	vector<int> ans;
	int i = 0 , j = f.size() - 1;
	while (i < j) {
		ans.emplace_back(f[i++]+f[j--]);
	}
	sort(ans.begin(), ans.end());

	cout << (*(ans.end()-1) - *(ans.begin())) <<endl;
	return 0;
}

发表于 2019-10-20 22:05:52 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int num[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;
    return 0;
}

发表于 2019-07-11 19:28:29 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a, a+n);
    int Min = INT_MAX, Max = INT_MIN;
    for(int i=0,j=n-1;i<j;i++,j--){
        Min = min(Min, a[i]+a[j]);
        Max = max(Max, a[i]+a[j]);
    }
    cout<<Max-Min<<endl;
    return 0;
}

发表于 2019-08-04 21:53:26 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool compare(int a, int b) {
    return a < b;
}
int main() {
    int n;
    cin >> n;
    vector<int> a;
    int number;
    for (int i = 0; i < n; i++)
    {
        cin >> number;
        a.push_back(number);
    }
    sort(a.begin(),a.end(),compare);
    vector<int> b;
    for (int i = 0; i < n/2; i++)
    {
        int sum1 = a[i] + a[n - 1 - i];
        b.push_back(sum1);
    }
    sort(b.begin(), b.end(), compare);
    cout << b[b.size() - 1] - b[0] << endl;
    return 0;
}
发表于 2021-02-05 17:29:10 回复(0)
只A了80%,应该是内存溢出了,有什么改进办法吗?
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int len = scanner.nextInt();
        int[] nums = new int[len];
        for(int i=0;i<len;i++){
            nums[i] = scanner.nextInt();
        }
 
        Arrays.sort(nums);
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i=0;i<(len/2-1);i++){
            int temp = nums[i] + nums[len-i-1];
            max = max < temp? temp : max;
            min = min > temp? temp : min;
        }
        System.out.println(max-min);
    }
}


发表于 2020-09-01 15:07:30 回复(0)
n = int(input())
 
nums = [int(i) for i in input().split()]
nums.sort()
minV = 201
maxV = 0
 
l, r = 0, n - 1
while l < r:
    t = nums[l] + nums[r]
    minV = min(minV, t)
    maxV = max(maxV, t)
    l += 1
    r -= 1
 
print(maxV - minV)

发表于 2020-08-01 16:48:23 回复(0)
n = int(input())

a = input().split()

b = []
for i in range(n):
    b.append(int(a[i]))

c = sorted(b)
d = []
for j in range(n//2):
    d.append(c[j] + c[n-1-j])

print(max(d)-min(d))

发表于 2020-06-28 22:06:11 回复(0)
n = int(input())
s = list(map(int, input().split()))
s = sorted(s)
c = []
for i in range(n//2):
    c = c + [s[i] + s[n - 1 - i]]
print(max(c) - min(c))

发表于 2020-05-02 18:36:08 回复(0)
# 1.排序
# 2.对有序数列头尾相加,让“和”尽量平均分布
# 根据题意,n应为偶数

n = int(input())
arr = list(map(int, input().split()))

arr.sort()

min_sum, max_sum = float('inf'), -100000

for i in range(len(arr)//2):
    res = arr[i]+arr[-1-i]
    max_sum = max(max_sum, res)
    min_sum = min(min_sum, res)
    
print(max_sum-min_sum)

编辑于 2020-04-25 21:32:34 回复(0)
谁能证明一下。。。
发表于 2020-04-09 11:50:28 回复(0)