输入总共两行。
第一行一个正整数,代表参加国际交流会的人数(即圆桌上所坐的总人数,不单独对牛牛进行区分)
第二行包含个正整数,第个正整数代表第个人的特征值。
其中
注意:
邻座的定义为: 第人的邻座为,第人的邻座是,第人的邻座是。
邻座的差异值计算方法为。
每对邻座差异值只计算一次。
输出总共两行。
第一行输出最大的差异值。
第二行输出用空格隔开的个数,为重新排列过的特征值。
(注意:不输出编号)
如果最大差异值情况下有多组解,输出任意一组即可。
4 3 6 2 9
20 6 2 9 3
这么坐的话
差异和为为最大的情况。
若排序后的序列为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; }
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))
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 + " "); } } }
排序后双指针交替输出即可
#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; } }
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 + " "); } } }
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=" ")
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=" ")
#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; }
个数分奇数和偶数,然后将其排序,大的存为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
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+" "); } } }