首页 > 试题广场 >

国际交流会

[编程题]国际交流会
  • 热度指数:1941 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
最近小强主办了一场国际交流会,大家在会上以一个圆桌围坐在一起。由于大会的目的就是让不同国家的人感受一下不同的异域气息,为了更好地达到这个目的,小强希望最大化邻座两人之间的差异程度和。为此,他找到了你,希望你能给他安排一下座位,达到邻座之间的差异之和最大。

输入描述:
输入总共两行。
第一行一个正整数,代表参加国际交流会的人数(即圆桌上所坐的总人数,不单独对牛牛进行区分)
第二行包含个正整数,第个正整数a_i代表第个人的特征值。
其中
注意:
邻座的定义为: 第的邻座为,第人的邻座是,第人的邻座是
邻座的差异值计算方法为
每对邻座差异值只计算一次。


输出描述:
输出总共两行。
第一行输出最大的差异值。
第二行输出用空格隔开的个数,为重新排列过的特征值。
(注意:不输出编号)
如果最大差异值情况下有多组解,输出任意一组即可。
示例1

输入

4
3 6 2 9

输出

20
6 2 9 3

说明

这么坐的话
差异和为\text |6-2|+|2-9|+|9-3|+|3-6|=20为最大的情况。

若排序后的序列为b, 则差异和为

如果将绝对值符号拆出来, 每个数会被运算两次, 有三种情况: 两次加, 一次加一次减, 两次减

其中加和减的数量一致, 当且仅当n为奇数时会出现一个数进行一次加一次减

所以我们希望两次加的情况尽可能给大的数, 两次减的情况给尽可能小的数, 此时就是最优解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
signed main() {
    int n; cin >> n;
    vector<int> a(n);
    for(int &t : a) cin >> t;
    sort(a.begin(), a.end());
    vector<int> b(n);
    for(int l = 0, r = n-1, i = 0; i < n; ++ i )
        if(i & 1) b[i] = a[l++];
        else b[i] = a[r--];
    int ans = 0;
    for(int i = 0; i < n; ++ i) 
        ans += abs(b[i] - b[(i+1)%n]);
    cout << ans << endl;
    for(int t : b) cout << t << " ";
    cout << endl;
}
发表于 2022-03-13 08:08:31 回复(0)
1. 将输入list排序
2. 分别取前一半和后一半生成list1和list2
3. 将list1或list2倒转
4. 将list1和list2相间合并
n=int(input())
x=list(map(int,(input().split())))
x.sort()
num_of_big=int(len(x)/2)
small=x[0:num_of_big]
big=x[num_of_big:]
small.reverse()
ans=[]
big_index=0
small_index=0
for i in range(n):
    if i%2==0:
        #插大数
        ans.append(big[big_index])
        big_index+=1
    else:
        ans.append(small[small_index])
        small_index+=1
diff=[abs(ans[i]-ans[i+1]) for i in range(n-1)]+[abs(ans[-1]-ans[0])]
print(sum(diff))
print(" ".join(str(i) for i in ans))


发表于 2021-07-08 21:53:48 回复(0)
将数组排序,利用双指针从头和尾依次选取最大和最小值存在为结果数组中,再求最大差值。

import java.util.*;

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);
        long maxSum = 0;
        int[] result = new int[n];
        int i = 0, j = n - 1, idx = 0;
        while (i < j) {
            result[idx++] = nums[i++];
            result[idx++] = nums[j--];
        }
        if (n % 2 == 1)
            result[idx] = nums[i];
        for (i = 1; i < n; i++) {
            maxSum += Math.abs(result[i] - result[i - 1]);
        }
        maxSum += Math.abs(result[0] - result[n - 1]);
        System.out.println(maxSum);
        for (int r : result) {
            System.out.print(r + " ");
        }
    }
}
发表于 2022-07-10 11:23:41 回复(0)

排序后双指针交替输出即可

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        vector<int> people(n);
        for(int i = 0; i < n; i++){
            cin >> people[i];
        }
        sort(people.begin(), people.end());
        vector<int> ans;
        int i = 0, j = n - 1;
        while(i <= j){
            if(i <= j) ans.push_back(people[i++]);
            if(i <= j) ans.push_back(people[j--]);
        }
        long sum = abs(ans[0] - ans[n - 1]);
        for(int i = 1; i < n; i++){
            sum += abs(ans[i] - ans[i - 1]);
        }
        cout << sum << endl;
        for(int i = 0; i < n; i++){
            cout << ans[i] << " ";
        }
        cout << endl;
    }
}
发表于 2022-03-13 12:26:17 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] features = new long[n];
        for(int i = 0; i < n; i++){
            features[i] = sc.nextLong();
        }
        
        // 从小到大排序
        Arrays.sort(features);
        
        // 从中间和最左边开始取,这样每次取的之间距离是相同的
        // 这样特征值相差最平均
        int mid = n / 2, i = 0;
        int j = mid;
        ArrayList<Long> seats = new ArrayList(n);
        long res = 0;
        while(i < mid && j < n){
            seats.add(features[j]);
            seats.add(features[i]);
            i++;
            j++;
        }
        if(j < n){
            seats.add(features[j]);
        }
        //计算差值和
        for(i = 1; i < n; i++){
            res += Math.abs(seats.get(i) - seats.get(i - 1));
        }
        res += Math.abs(seats.get(0) - seats.get(seats.size() - 1));
        System.out.println(res);
        for(Long s : seats){
            System.out.print(s + " ");
        }
    }
}


发表于 2021-06-09 09:30:22 回复(0)
#对称的插入
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
tmp = []
if n % 2 == 0:
    p2 = n // 2
else:
    p2 = n // 2 + 1
p1 = 0
index = p2
while p1 < index and p2 < n:
    tmp.append(arr[p1])
    p1 += 1
    tmp.append(arr[p2])
    p2 += 1
if p1 < index:
    tmp.append(arr[p1])
ans = 0
for i in range(n - 1):
    ans += abs(tmp[i] - tmp[i + 1])
ans += abs(tmp[0] - tmp[n - 1])
print(ans)
for i in tmp:
    print(i, end=" ")

发表于 2021-05-06 12:45:04 回复(0)
这道题可能超时,我觉得是输出没有规范,然后后台一直循环右移对比导致的。。。。。当输出的模式跟标准一毛一样的时候就不超时了。
编辑于 2021-04-29 16:37:40 回复(2)
要想相邻元素的绝对差之和最大,就要保证所有数对的绝对差尽可能均匀分布。进行如下操作就可以达到这个效果:
先将数组进行排序,然后将其分为前后两个子数组,按顺序取出两个子数组的元素组成数对。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;

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 midIdx = n % 2 == 0? n / 2: n / 2 + 1;
        int ptr1 = 0, ptr2 = midIdx;
        ArrayList<Integer> list = new ArrayList<>();
        while(ptr1 < midIdx && ptr2 < n){
            list.add(arr[ptr1 ++]);
            list.add(arr[ptr2 ++]);
        }
        if(ptr1 < midIdx) list.add(arr[ptr1]);
        if(ptr2 < n) list.add(arr[ptr2]);
        long sum = 0;
        for(int i = 0; i < n - 1; i++) sum += Math.abs(list.get(i + 1) - list.get(i));
        System.out.println(sum + Math.abs(list.get(0) - list.get(n - 1)));
        for(int i = 0; i < n; i++) System.out.print(list.get(i) + " ");
    }
}
这个题不知道为什么用scala的时候cpu时间总是超,用python再写一个版本
n = int(input())
nums = sorted(list(map(int, input().split())))
medianIdx = n // 2 if n % 2 == 0 else n // 2 + 1
i, j = 0, medianIdx
ans = []
while i < medianIdx and j < n:
    ans.append(nums[j])
    ans.append(nums[i])
    i += 1
    j += 1
if i < medianIdx:
    ans.append(nums[i])
if j < n:
    ans.append(nums[j])
maxDiff = 0
for k in range(n - 1):
    maxDiff += abs(ans[k + 1] - ans[k])
maxDiff += abs(ans[n - 1] - ans[0])
print(maxDiff)
for num in ans:
    print(num, end=" ")

编辑于 2021-08-25 18:00:38 回复(0)
#include<iostream>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll Abs(ll a,ll b)
{
    if(a>=b) return a-b;
    else return b-a;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int n,p1,p2,index;
    ll ans=0;
    cin>>n;
    ll a[n];
    vector<ll> tmp;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n); //smaller--->larger
    if(n%2==0) p2=n/2;
    else p2=n/2+1;
    p1=0;
    index=p2;
    while(p1<index && p2<n)
    {
        tmp.push_back(a[p1]);
        p1+=1;
        tmp.push_back(a[p2]);
        p2+=1;
    }
    if(p1<index) tmp.push_back(a[p1]);
    for(int i=0;i<n-1;i++) 
    {
        ans+=Abs(tmp[i],tmp[i+1]);
    }
    ans+=Abs(tmp[0],tmp[n-1]);
    cout<<ans<<endl;
    for(int i:tmp) 
    {
        cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}

发表于 2021-06-02 14:22:42 回复(0)
个数分奇数和偶数,然后将其排序,大的存为L1,小的存为L2,然后将其逐个添加到新列表中,在计算,但是不晓得为什么就只有40的通过率,也没有反例


while True:
    try:
        a=int(input())
        L=list(map(int ,input().split()))
        L.sort()
        d=[]
        res=0

        if a%2==0:
            L1=L[:len(L)//2]
            L2=L[len(L)//2:]
            L1.sort(reverse=True)
            for i in range(a//2):
                d.append(L1[i])
                d.append(L2[i])
            for i in range(a):
                res+=abs(d[i]-d[i-1])
        else:
            L1=L[:len(L)//2]
            L1.sort(reverse=True)
            L2=L[len(L)//2+1:]
            for i in range(a//2):
                d.append(L2[i])
                d.append(L1[i])
            d.append(L2[-1])
            for i in range(a):
                res+=abs(d[i]-d[i-1])
        print(res)
        print(' '.join(map(str,d)))

    except:
        break



发表于 2021-05-26 14:53:48 回复(0)
贪心算法
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= Integer.parseInt(sc.nextLine());
        String[] strs = sc.nextLine().split(" ");
        long[] d = new long[n];
        long[] t = new long[n];
        for (int i = 0; i < n; i++) {
            d[i] = Long.parseLong(strs[i]);
        }
        Arrays.sort(d);
        int p = 0, q = d.length-1;
        int i = 0;
        long cost = 0;
        boolean f = false;

        t[i++] = d[q--];
        while (p < q){
            if(f) {
                t[i] = d[q--];
                cost += Math.abs(t[i] - t[i-1]);
                f=false;
            }else {
                t[i] = d[p++];
                cost += Math.abs(t[i] - t[i-1]);
                f=true;
            }
            i++;
        }
        t[i] = d[p];
        cost += Math.abs(t[i] - t[i-1]);
        cost += Math.abs(t[i] - t[0]);

        System.out.println(cost);
        for (long l : t) {
            System.out.print(l+" ");
        }

    }
}


编辑于 2021-05-12 21:34:22 回复(0)