输入包括两行,第一行一个整数n(1 ≤ n ≤ 50),表示学生的人数 第二行为n个整数h[i](1 ≤ h[i] ≤ 1000),表示每个学生的身高
输出一个整数,表示n个学生列队可以获得的最大的疯狂值。 如样例所示: 当队列排列顺序是: 25-10-40-5-25, 身高差绝对值的总和为15+30+35+20=100。 这是最大的疯狂值了。
5 5 10 25 40 25
100
#include <iostream> #include <vector> #include <algorithm> using namespace std; int* Bubble_Sort(int* h, int n){ int low = 0; int high = n - 1; //设置变量的初始值 int tmp, j; while (low < high) { for (j = low; j< high; ++j) //正向冒泡,找到最大者 if (h[j]> h[j + 1]) { tmp = h[j]; h[j] = h[j + 1]; h[j + 1] = tmp; } --high; //修改high值, 前移一位 for (j = high; j>low; --j) //反向冒泡,找到最小者 if (h[j]<h[j - 1]) { tmp = h[j]; h[j] = h[j - 1]; h[j - 1] = tmp; } ++low; //修改low值,后移一位 } return h; } int main(){ //输入 int n = 0; cin >> n; int h[50] = {0}; for (int i = 0; i < n; i++) cin >> h[i]; int ans = 0; int* sort_h; sort_h = Bubble_Sort(h,n); // 偶数 if (n % 2 == 0) { for (int i = 0; i < n / 2; i++) ans += (sort_h[n - i - 1] - sort_h[i]); ans = ans * 2 + sort_h[n/2 - 1] - sort_h[n/2]; } // 奇数 else { for (int i = 0; i < n / 2; i++) { ans += (sort_h[n - i - 1] - sort_h[i]); } ans = ans * 2 + sort_h[n/2 - 1] - sort_h[n/2 + 1]; (abs(sort_h[n / 2 + 1] - sort_h[n / 2]) > abs(sort_h[n / 2] - sort_h[n / 2 - 1])) ? (ans += abs(sort_h[n / 2 + 1] - sort_h[n / 2])) : (ans += abs(sort_h[n / 2] - sort_h[n / 2 - 1])); } //输出ans cout << ans; return 0; }
#include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> a(n, 0); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end()); int i = 0; int j = n - 1; int ret = abs(a[0] - a[n - 1]); while (i <= n / 2 - 2) ret += abs(a[i] - a[j - 1]) + abs(a[(i++) + 1] - a[(j--)]); if (n % 2 == 1) ret += max(abs(a[(n-1)/2-1]-a[(n-1)/2]),abs(a[(n-1)/2+1]-a[(n-1)/2])); cout << ret << endl; return 0; }
n = int(input()) l = list(map(int,input().split())) l.sort() temp =[l[0]] left = 1 right = n-1 res = 0 while left<=right: r0 = abs(temp[0] - l[right]) lr = abs(temp[-1] - l[right]) l0 = abs(temp[0]-l[left]) l1 = abs(temp[-1]-l[left]) tl = [r0,lr,l0,l1] m = max(tl) if tl.index(m)==0: temp.insert(0,l[right]) right-=1 if tl.index(m)==1: temp.append(l[right]) right-=1 if tl.index(m)==2: temp.insert(0,l[left]) left+=1 if tl.index(m)==3: temp.append(l[left]) left+=1 for i in range(n-1): res+=abs(temp[i+1]-temp[i]) print(res)
//又是找规律,例子中两个25感觉就是个坑,就是先放入大的,大的两边放小的,然后在次大的,然后...... #include <iostream> #include <algorithm> #include <deque> using namespace std; void Judge(deque<int> &arr,deque<int> &result, int i) { if(i%2 == 0) { result.push_back(arr[0]); arr.pop_front(); //这里如果不加判断,则如1 1 1 1 1 1 1 500 500 500 500 1000 1000 1000 1000就会出错,因为按照顺序来就错啦,所以最后一个需要进行判断; if(arr.size() == 1 && (abs(arr[0] - result[0]) < abs(result[result.size() - 1] - arr[0]))) { result.push_back(arr[0]); } else result.push_front(arr[0]); arr.pop_front(); } else { result.push_back(arr[arr.size() - 1]); arr.pop_back(); if(arr.size() == 1 && (abs(arr[0] - result[0]) < abs(result[result.size() - 1] - arr[0]))) { result.push_back(arr[0]); } else result.push_front(arr[arr.size() - 1]); arr.pop_back(); } } int main() { deque<int> arr, result; int sum = 0; int count = 0; int input; int n; cin>>n; while(cin>>input) { arr.push_back(input); } sort(arr.begin(), arr.end()); result.push_back(arr[n - 1]); arr.pop_back(); if(n % 2 == 0) { for(int i = 0; i < (n - 2)/2; i++) { Judge(arr, result, i); } result.push_back(arr[0]); } else { for(int i = 0; i < (n - 1)/2; i++) { Judge(arr, result, i); } } for(int i = 1; i < n; i++) { count = result[i] - result[i - 1]; sum = sum + abs(count); } cout << sum << endl; return 0; }
占用内存:3568k
"""" 思路:先将height排序,每一次取出最小值和最大值放在队列中 然后再取出最小值和最大值,最小值放在上次最大值的右边 最大值放在上次最小值的左边 Note:需要判断输入个数的奇偶性,若是奇数,最后一个元素 是防止在队头或者队尾,需要和当前的队头和队尾元素比较 eg1: 25-10-40-5-25(n为奇数) sort:5-10-25-25-40 第一次取出min=5,max=40 queue:[5,40] 第二次取出min=10,max=25 queue:[25,5,40,10] 第三次取出25,放在队头or队尾?明显放在队尾差异更大 queue:[25,5,40,10,25] res = 20+35+30+15=100 eg2:1-2-4-8-6-10(n为偶数) sort:1-2-4-6-8-10 第一次取出min=1,max=10 queue:[1,10] 第一次取出min=2,max=8 queue:[8,1,10,2] 第一次取出min=4,max=6 queue:[4,8,1,10,2,6] res = 4+7+9+8+4=32 """ n = int(input()) height = list(map(int,input().split())) height.sort() min_value = height[0] max_value = height[-1] res = abs(max_value-min_value) # 队头指针 top = 1 # 队尾指针 rear = n-2 while top<=rear: # 当n为奇数时,最后一步top==rear if top==rear: res += max(abs(min_value-height[top]),abs(max_value-height[rear])) else: # 计算右边差距 res += abs(max_value-height[top]) # 计算左边差距 res += abs(min_value-height[rear]) # update min and max min_value = height[top] max_value = height[rear] # 移动指针 top += 1 rear -=1 print(res)
#include <iostream> #include <vector> #include <deque> #include <algorithm> using namespace std; int main() { int n; cin>>n; vector<int> a; for (int i=0;i<n;i++){ int temp; cin>>temp; a.push_back(temp); } sort(a.begin(),a.end()); deque<int> b; int i=0; int j=n-1; int cnt=0; while(i<j){ if (cnt%2==0 && i<j) { b.push_back(a[j--]); b.push_front(a[i++]);} else if (cnt%2==1 && i<j) { b.push_back(a[i++]); b.push_front(a[j--]); } cnt++; } if(i==j)//如果i=j,就是有奇数个的情况 { if(abs(a[i]-b[0])>abs(a[i]-b[n-2])){ b.push_front(a[i]);} else{ b.push_back(a[i]);} } int res=0; for (int i=1;i<b.size();i++){ res+=abs(b[i]-b[i-1]); } cout<<res<<endl; return 0; }
//AC代码: #include<stdio.h> #include<algorithm> #include<vector> #include<math.h> #include<queue> using namespace std; int main(){ int N,i,a[100]; //freopen("input.txt","r",stdin); while(scanf("%d",&N)!=EOF){ for(i=0;i<N;i++) scanf("%d",&a[i]); vector<int> d(N); sort(a,a+N); deque<int> Q; Q.push_back(a[N-1]); int l=0,r=N-2,flag=1; while(l<r){ int cnt=1,a1,a2; if(flag==1){ a1=a[l++]; if(l<r) a2=a[l++],cnt++; }else{ a1=a[r--]; if(l<r) a2=a[r--],cnt++; } if(cnt==1) abs(Q.front()-a1)<abs(Q.back()-a1)?Q.push_back(a1):Q.push_front(a1); else{ if(abs(Q.front()-a1)+abs(Q.back()-a2)<abs(Q.front()-a2)+abs(Q.back()-a1)){ Q.push_front(a2); Q.push_back(a1); }else{ Q.push_front(a1); Q.push_back(a2); } } flag=!flag; } if(l==r) abs(Q.front()-a[l])<abs(Q.back()-a[l])?Q.push_back(a[l]):Q.push_front(a[l]); int pre=Q.front(),res=0; Q.pop_front(); while(!Q.empty()){ res+=abs(Q.front()-pre); pre=Q.front(); Q.pop_front(); } printf("%d\n",res); } }//双端队列,前插后插,乱搞,过了
//血的教训,就算调不出来最后那个bug,也至少得90%,然而考试只过了20%,boom! //总体思路:先放最大的数,然后两边放最小的数,再两边放次大和次次大的数, //再两边放小的数...直到放完,最后要检查一下两边的元素位置是否合适,不合适的话移动一下 #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { int n; while(cin>>n) { vector<int> a(n); for(int i=0;i<n;++i) cin>>a[i]; if(1==n) { cout<<a[0]<<endl; return 0; } sort(a.begin(),a.end()); vector<int> b; //b.reserve(n); b.push_back(a[n-1]); int left=-1; int right=n-1; int flag=1; while(left+1<right) { if(flag) { b.insert(b.begin(),a[++left]); if(left<right) b.push_back(a[++left]); } else { b.insert(b.begin(),a[--right]); if(left<right) b.push_back(a[--right]); } flag^=1; } //这段代码是检测最后一个元素的放置的位置是否合适,不合适的话移到最前面 //如果没有这一步检查,只能过90% if(abs(b[n-1]-b[n-2])<abs(b[n-1]-b[0])) { int tmp=b[n-1]; b.erase(b.end()-1); b.insert(b.begin(),tmp); } int h=0; for(int i=1;i<n;++i) { h+=abs(b[i]-b[i-1]); } cout<<h<<endl; } return 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 left = 0, right = n - 1; int maxValue = arr[right] - arr[left]; int preMax = arr[right]; int preMin = arr[left]; left ++; right --; while(left < right){ maxValue += preMax + arr[right] - preMin - arr[left]; preMin = arr[left]; preMax = arr[right]; left ++; right --; } if(left == right) maxValue += Math.max(arr[right] - preMin, preMax - arr[left]); System.out.println(maxValue); } }
逆向排序,分成较大部分和较小部分。再分奇偶讨论即可。
import math def solve(nums): if len(nums) == 1: return nums[0] nums = sorted(nums, reverse=True) length = len(nums) max_part = nums[0: math.ceil(length / 2)] min_part = nums[math.ceil(length / 2):] if len(nums) % 2 == 0: return 2 * sum(max_part[:-1]) + max_part[-1] - 2 * sum(min_part[1:]) - min_part[0] else: return 2 * sum(max_part[:-2]) + max_part[-2] + max_part[-1] - 2 * sum(min_part)
while True: try: n=int(input()) h=sorted(list(map(int,input().split()))) Max,Min,res=0,0,0 if n%2==1: while(len(h)>1): res+=h[-1]-Min+Max-h[0] Min=h.pop(0) Max=h.pop(-1) res+=max(abs(h[0]-Min),abs(h[0]-Max)) print(res) else: while(len(h)>0): res+=h[-1]-Min+Max-h[0] Min=h.pop(0) Max=h.pop(-1) print(res) except: break
# 先写出一部分在进行公式推导,可分为长度为偶数和奇数的情况,奇数又可以分为ABAB和BABA的情况 def crazy(n: int, h: [int]) -> int: if n == 1: return 0 else: h = sorted(h) if n%2 == 0: return 2*sum(h[n//2+1:]) + h[n//2] - 2*sum(h[:n//2-1]) -h[n//2-1] # 人数为偶数 else: t1 = 2*sum(h[n//2+1:]) - 2*sum(h[:n//2-1]) - sum(h[n//2-1:n//2+1]) # 人数为奇数,且较小的数在较大的数后面 t2 = 2*sum(h[n//2+2:]) + sum(h[n//2:n//2+2]) - 2*sum(h[:n//2]) # 人数为奇数,且较大的数在较小的数后面 return max(t1, t2) if __name__ == "__main__": n = int(input()) h = list(map(int, input().split())) print(crazy(n, h))
#include <bits/stdc++.h> using namespace std; int main(){ int n; scanf("%d", &n); int a[n]; for(int i=0;i<n;i++) scanf("%d", &a[i]); sort(a, a+n); int Max=a[n-1], Min=a[0], l=1, r=n-2, s=Max-Min; while(l<r){ s += (Max-a[l]) + (a[r]-Min); Min = a[l++]; Max = a[r--]; } s += max(Max-a[l], a[r]-Min); printf("%d\n", s); return 0; }
#include <bits/stdc++.h> using namespace std; int a[55], mark[55]; deque<int> d; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); d.push_back(a[n - 1]); mark[n - 1] = 1; int total = n - 1; while(total) { int Max = 0, idx = 0; for (int i = 0; i < n; i++) { if (!mark[i]) { int tmp = max(abs(a[i] - d.front()), abs(a[i] - d.back())); if (tmp > Max) { idx = i; Max = tmp; } } } mark[idx] = 1; total--; if (abs(a[idx] - d.front()) > abs(a[idx] - d.back())) { d.push_front(a[idx]); } else { d.push_back(a[idx]); } } int ans = 0; for (int i = 1; i < (int)d.size(); i++) { ans += abs(d.at(i) - d.at(i - 1)); } cout << ans << "\n"; return 0; }
n = int(input())
while True: try: n = int(input()) except: break h = list(map(int, input().split())) h.sort() if len(h) < 2: print(0) continue q = [h.pop()] flag = 0 while len(h) > 2: if flag == 0: h1 = h.pop(0) h2 = h.pop(0) flag = 1 else: h1 = h.pop() h2 = h.pop() flag = 0 if abs(h1 - q[0]) + abs(h2 - q[-1]) > abs(h1 - q[-1]) + abs(h2 - q[0]): q.insert(0, h1) q.append(h2) else: q.insert(0, h2) q.append(h1) if len(h) == 1: h1 = h.pop() if abs(h1 - q[0]) > abs(h1 - q[-1]): q.insert(0, h1) else: q.append(h1) elif len(h) == 2: h1 = h.pop() h2 = h.pop() case1 = abs(h1 - q[0]) case2 = abs(h1 - q[-1]) case3 = abs(h2 - q[0]) case4 = abs(h2 - q[-1]) case = max(case1, case2, case3, case4) if case == case1 or case == case2: if case == case1: q.insert(0, h1) elif case == case2: q.append(h1) if abs(h2 - q[0]) > abs(h2 - q[-1]): q.insert(0, h2) else: q.append(h2) else: if case == case3: q.insert(0, h2) else: q.append(h2) if abs(h1 - q[0]) > abs(h1 - q[-1]): q.insert(0, h1) else: q.append(h1) res = 0 for i in range(len(q) - 1): res += abs(q[i] - q[i+1]) print(res)
#include<iostream> #include<stdio.h> #include<algorithm> #include<cstring> #include<vector> #include<math.h> using namespace std; int n; int h[51]; int main(){ cin >> n; //相邻学生身高差的绝对值组合 for(int i = 0; i < n; i++){ cin >> h[i]; } if(n == 1){ cout << 0 << endl; return 0; } else if(n == 2){ cout << abs(h[1] - h[0]) << endl; return 0; } //排序 sort(h, h + n); int sum1 = 0; int sum2 = 0; //n为偶数 只有一种情况 if(n % 2 == 0){ int k = n / 2; sum1 = h[k]; for(int i = k + 1; i < n; i++){ sum1 += 2 * h[i]; } for(int i = 0; i <= k - 2; i++){ sum1 -= 2 * h[i]; } sum1 -= h[k - 1]; } //n为奇数 有两种情况 else{ int k = n / 2; for(int i = k + 1; i < n; i++){ sum1 += 2 * h[i]; } for(int i = 0; i <= k - 2; i++){ sum1 -= 2 * h[i]; } sum1 -= h[k]; sum1 -= h[k - 1]; sum2 = h[k]; for(int i = k + 2; i < n; i++){ sum2 += 2 * h[i]; } for(int i = 0; i <= k - 1; i++){ sum2 -= 2 * h[i]; } sum2 += h[k + 1]; } cout << max(sum1, sum2) << endl; return 0; }
// 又是找规律分为 高低高低高,地高低高低;高低高低高低(低高低高低高)3种 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] h = new int[n]; for(int i = 0; i < n; i++) h[i] = sc.nextInt(); sc.close(); int res = 0; Arrays.sort(h); if(n == 1){System.out.println(h[0]); return;} if((n&1) == 0){// 偶数 int m = n>>1; for(int i = 0; i < m; i++) res += (h[i+m] - h[i]); res *= 2; res -= (h[m] - h[m-1]); } else{// 奇数 // 高低高低高,中位数归高,中位数右边的那个数只加一次 // 低高低高低,中位数归低,中位数左边的那个数只减一次 int m = n>>1; for(int i = 0; i < m; i++) res += (h[i+m+1] - h[i]); res *= 2; res += h[m-1] - h[m] > h[m] - h[m+1] ? h[m-1] - h[m] : h[m] - h[m+1]; } System.out.println(res); } }