首页 > 试题广场 >

两两配对差值最小

[编程题]两两配对差值最小
  • 热度指数：8307 时间限制：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
算法知识视频讲解
添加回答
逐梦star头像 逐梦star 
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)
Python
我要扛offer回家头像 我要扛offer回家 
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)
Robust-neu头像 Robust-neu 
#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)
Python
卷积神经网络哦头像 卷积神经网络哦
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)
pein531头像 pein531
贪心思想：如果让大的和大的配对，小的和小的配对，那么最大值和最小值的差距将会进一步拉大，因此尽可能让大的和小的配对，这样最大值和最小值的差距才会缩小，数对之和的分布也会尽可能平均。 
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)
LHC0512头像 LHC0512

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)
buptee头像 buptee
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)
dragonlogin头像 dragonlogin 
#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)
无心2019头像 无心2019 
#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)
C/C++
nbgao头像 nbgao 
#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)
abbbe头像 abbbe
为什么这样就能保证差值最小呢？想严格证明一下，没有想出方法orz
发表于 2020-02-13 00:24:24 回复(1)
及时行乐的老实人头像 及时行乐的老实人 
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);
    }
}我不明白呀  这个题目不是让求最小的差值吗？为什么这里取max（配对和）-min（配对和）？这不应该是差值最大的吗？
发表于 2024-08-18 22:29:08 回复(0)
Java
南侠头像 南侠
贪心是不错，就是不太好证明。只能用“平均”的思想浅浅理解了。 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Collections;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            List<Integer> arr = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                arr.add(in.nextInt());
            }
            Collections.sort(arr);
            //
            int mi = 200 + 5;
            int mx = -1;
            int i = 0, j = n - 1;
            while (i < j) {
                int k = arr.get(j) + arr.get(i);
                mi = Math.min(mi, k);
                mx = Math.max(mx, k);
                i++;
                j--;
            }
            System.out.print(mx - mi);
        }
    }
}

发表于 2023-11-29 17:09:18 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main

import (
    "fmt"
    "sort"
)

func main() {
    var n int
    fmt.Scan(&n)
    arr:=make([]int,n)
    for i:=0;i<n;i++{
        fmt.Scan(&arr[i])
    }
    sort.Ints(arr)
    sum:=make([]int,n/2)
    i,j:=0,n-1
    for i<j{
        sum[i]=arr[i]+arr[j]
        i++
        j--
    }
    sort.Ints(sum)
    fmt.Print(sum[i-1]-sum[0])
}

发表于 2023-03-18 11:58:33 回复(0)
黑奇居子头像 黑奇居子 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < nums.length; i++){
            nums[i] = in.nextInt();
        }
        Arrays.sort(nums);
        int left = 0, right = nums.length-1;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int[] temp = new int[n/2];
        for(int i = 0; i < n / 2; i++){
            temp[i] = nums[left] + nums[right];
            left++;
            right--;
            max = Math.max(temp[i], max);
            min = Math.min(temp[i], min);
        }
        System.out.print(max - min);
        
    }
}

发表于 2023-03-08 11:31:24 回复(0)
牛客476721401号头像 牛客476721401号
var num=parseInt(readline());
var arr=readline().split(' ')
var arr1=arr.map(Number).sort((a,b)=>a-b);
 
var arr2=[];
for(let i=0;i<num/2;i++){
   arr2[i]=arr1[i]+arr1[num-i-1];
}
 
console.log( (Math.max(...arr2)- Math.min(...arr2))   )
发表于 2021-09-21 21:15:20 回复(0)
Java
再向前一点头像 再向前一点
排序+左右指针 
import java.util.Scanner;
import java.util.Arrays;
import java.lang.Math;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++){
            nums[i] = in.nextInt();
        }
        Arrays.sort(nums);
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int left = 0;
        int right = n-1;
        while(left<right){
            int sum = nums[left]+nums[right];
            max = Math.max(max,sum);
            min = Math.min(min,sum);
            left++;
            right--;
        }
        System.out.println(max-min);
    }
}


发表于 2021-08-24 10:07:48 回复(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)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 数组 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 排序 贪心 2019 拼多多集团-PDD Java工程师
上传者：小小
难度：
43条回答 16488浏览

热门推荐

通过挑战的用户

查看代码

相关试题

两两配对差值最小

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号