选择两个元素,一个加 1,另一个减 1。
小美希望若干次操作后,众数的出现次数尽可能多。你能帮她求出最小的操作次数吗?
众数定义:在一组数据中,出现次数最多的数据,是一组数据中的原数据,而不是相应的次数。 一组数据中的众数不止一个,如数据2、3、-1、2、1、3中,2、3都出现了两次,它们都是这组数据中的众数。
第一行为一个正整数,代表数组的大小。
第二行输入个正整数,代表小美拿到的数组。
一个整数,代表最小的操作次数。
3 1 4 4
2
第一次操作:第一个数加 1,第二个数减 1。第二次操作:第一个数加 1,第三个数减 1。数组变成[3,3,3],众数出现了 3 次。
3 1 5 5
0
众数出现了 2 次,由于无法再用操作使得众数出现的次数变得更多,所以无需操作。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<long long> nums(n); for (int i=0; i<n; ++i) { cin >> nums[i]; } long long sum = accumulate(nums.begin(), nums.end(), (long long)0); if (sum%n==0) { long long avg = sum/n; long long ans = 0; for (auto a:nums) { ans += abs(a-avg); } cout << ans/2 << endl; return 0; } sort(nums.begin(), nums.end()); function<long long(vector<long long>&, int, int)> comp = [&](vector<long long>& nums, int l, int r) { long long tot = 0; for (int i=l; i<=r; ++i) { tot += nums[i]; } long long avg = tot/(r-l+1); long long avg2 = avg+1; long long a = 0; long long b = 0; long long c = 0; long long d = 0; for (int i=l; i<=r; ++i) { if (nums[i]>=avg) a+=nums[i]-avg; else b+=avg-nums[i]; if (nums[i]>=avg2) c+=nums[i]-avg2; else d+=avg2-nums[i]; } return min(max(a, b), max(c, d)); }; long long res1 = comp(nums, 0, n-2); long long res2 = comp(nums, 1, n-1); cout << min(res1, res2) << endl; return 0; } // 64 位输出请用 printf("%lld")
天呐 天呐 这道题卡了我一天,终于30个全部通过了!!感谢评论区的大佬,参照了评论的思路 Scanner sc = new Scanner(System.in); long leastTimes = 0; //最终结果 int n = 0; //数组个数 n = sc.nextInt(); long[] arr = new long[n]; int t = 0; //输入该数组 while (t < n) { arr[t++] = sc.nextInt(); } //求数组之和 long sum = 0; for (long j : arr) { sum += j; } long avg = sum / arr.length;//平均数 //平均数为整数 if (sum % arr.length == 0) { for (int i = 0; i < arr.length; i++) { leastTimes += Math.abs(arr[i] - avg); } System.out.println(leastTimes / 2); return; } //平均数除不清 else { sum = 0; Arrays.sort(arr); long[] newArr = new long[arr.length - 1]; //去掉垃圾数之后的数组 long leastTimes2 = 0; //取最小数为垃圾数 for (int i = 0; i < arr.length - 1; i++) { newArr[i] = arr[i + 1]; sum += arr[i + 1]; } avg = sum / newArr.length;//新数组的平均数 //新数组平均数为整数 if (sum % (newArr.length) == 0) { //各个数据到平均数的距离之和除以2 for (long j : newArr) { leastTimes += Math.abs(avg - j) ; } leastTimes /= 2; } else { long plus = 0; long minus = 0; //众数为avg for (int i = 0; i < newArr.length; i++) { //加操作数次数 if (avg > newArr[i]) { plus += avg - newArr[i]; } //减操作数次数 else { minus += newArr[i] - avg; } } leastTimes = Math.max(plus, minus); plus = 0; minus = 0; //众数为avg+1 avg+=1; for (int i = 0; i < newArr.length; i++) { //加操作数次数 if (avg > newArr[i]) { plus += avg - newArr[i]; } //减操作数次数 else { minus += newArr[i] - avg; } } leastTimes = Math.min(leastTimes, Math.max(plus, minus)); } sum=0; //取最大数为垃圾数 for (int i = 0; i < arr.length - 1; i++) { newArr[i] = arr[i]; sum += arr[i]; } avg = sum / newArr.length;//新数组的平均数 //新数组平均数为整数 if (sum % (newArr.length) == 0) { //各个数据到平均数的距离之和除以2 for (long j : newArr) { leastTimes2 += Math.abs(avg - j) ; } leastTimes2 /= 2; } else { long plus = 0; long minus = 0; //众数为avg for (int i = 0; i < newArr.length; i++) { //加操作数次数 if (avg > newArr[i]) { plus += avg - newArr[i]; } //减操作数次数 else { minus += newArr[i] - avg; } } leastTimes2 = Math.max(plus, minus); plus = 0; minus = 0; //众数为avg+1 avg+=1; for (int i = 0; i < newArr.length; i++) { //加操作数次数 if (avg > newArr[i]) { plus += avg - newArr[i]; } //减操作数次数 else { minus += newArr[i] - avg; } } leastTimes2 = Math.min(leastTimes2, Math.max(plus, minus)); } System.out.print(Math.min(leastTimes, leastTimes2)); }
def back(ls, index): ls.pop(index) n = len(ls) avg_1 = round(sum(ls) / n) high = 0 for num in ls: if num > avg_1: high += (num - avg_1) high_2 = 0 for num in ls: if num < avg_1: high_2 += abs(num - avg_1) high = max(high_2, high) return high def max_zhongshu(n, ls): if sum(ls)%n==0: avg = sum(ls)//n high = 0 for num in ls: if num>avg: high+=(num-avg) print(high) else: max_num = max(ls) max_index = ls.index(max_num) min_num = min(ls) min_index = ls.index(min_num) ls_copy = ls.copy() a = back(ls, max_index) b = back(ls_copy, min_index) print(min(a, b))
import java.util.*; import java.io.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(bf.readLine()); String[] str = bf.readLine().split(" "); long[] nums = new long[n]; long sum=0; for(int i=0;i<n;i++){ nums[i]=Long.parseLong(str[i]); sum+=nums[i]; } //System.out.println("sum="+sum+",sum%n="+(sum%n)); if((sum%n)==0){ long avg = sum/n; long step =0; for(int i=0;i<n;i++){ if(nums[i]>avg){ step+=nums[i]-avg; } } System.out.println(step); return; } Arrays.sort(nums); long res =Long.MAX_VALUE; long removeBigSum = sum-nums[n-1]; long removeSmallSum = sum-nums[0]; //去掉最大值,剩下的值取平均作为最终的众数。如果剩下的平均不是整数,取两边相邻的整数分别计算 //如平均值为23.1,那么就计算23和24两种情况 long bigRes = Long.MAX_VALUE; long avg = removeBigSum/(n-1); long step =0; for(int i=0;i<n-1;i++){ if(nums[i]>avg){ step+=nums[i]-avg; } } //System.out.println("removeBigSum="+removeBigSum+",step="+step); bigRes=Math.min(bigRes, step); if((removeBigSum%(n-1)) != 0){ step =0; avg = (removeBigSum/(n-1))+1; for(int i=0;i<n-1;i++){ if(nums[i]<avg){ step+=avg-nums[i]; } } //System.out.println("removeBigSum="+removeBigSum+",step="+step); bigRes=Math.min(bigRes, step); } //去掉最小值,剩下的值取平均作为最终的众数。如果剩下的平均不是整数,取两边相邻的整数分别计算 //如平均值为23.1,那么就计算23和24两种情况 long smallRes = Long.MAX_VALUE; avg = removeSmallSum/(n-1); step =0; for(int i=1;i<n;i++){ if(nums[i]>avg){ step+=nums[i]-avg; } } //System.out.println("removeSmallSum="+removeSmallSum+",step="+step); smallRes=Math.min(smallRes, step); if((removeSmallSum%(n-1)) != 0){ step =0; avg = (removeSmallSum/(n-1))+1; for(int i=1;i<n;i++){ if(nums[i]<avg){ step+=avg-nums[i]; } } //System.out.println("removeSmallSum="+removeSmallSum+",step="+step); smallRes=Math.min(smallRes, step); } res = Math.min(smallRes, bigRes); System.out.println(res); } }
public class m2024Code2Version2 { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 //如果 sum / n 可以整除,说明平均数可以作为众数 // 尽可能在数组中找到可以凑成 sum / 个数 满足整除的子集 数组 int n = in.nextInt(); long[] nums = new long[n]; long sum = 0; for (int i = 0; i < n; i++) { nums[i] = in.nextInt(); sum += nums[i]; } long count = 0; if (sum % n == 0) { //可以整除的情况 long avg = sum / n; //平均数 for (int i = 0; i < n; i++) { count += Math.abs(nums[i] - avg); } System.out.print(count / 2); return; } // 如果不能整除,说明不能使众数出现n次, 贪心思想,排除原数组的最大值或最小值,计算剩下的n-1个元素能否被均分, // 能均分众数就是 sum_part / (n -1) 不能均分 一种也是 sum_part / (n-1)向下取整, 或者 sum_part / (n-1)向下取整 + 1 // 解释一下 3 3 3 4 9 ; 原数组不能整除,选择9作为垃圾数, 3 + 3 + 3 + 4 / 4 = 3.25 一种众数是向下取整3 一种众数是 3 + 1 = 4 明显3,即向下取整 // 3 3 3 1 9 ; 选择9作为垃圾数 3 + 3 + 3 + 1 / 4 = 2.5 一种总数是向下取整2 一种众数是 2 + 1 = 3 明显3,即取整后+1 // 3 + 3 + 3 + 2 / 4 = 2.75 2 + 1 = 3 // 新思路:能否不针对两种 avg计算, 3.25 -> 0.25 < 0.5, 向下取整,调整次数更少 2.5 -> 0.5 >=0.5 适合+1 // 四舍五入 Arrays.sort(nums); //排序 long res1 = compare(0, nums, sum); long res2 = compare(nums.length - 1, nums, sum); System.out.print(Math.min(res1, res2)); } private static long compare(int del, long[] nums, long sum) { sum -= nums[del]; // 移除最大或最小元素 long avg = Math.round( (double) sum / (nums.length - 1) ); // 四舍五入 // long avg2 = sum / (nums.length - 1) + 1; // System.out.println("avg = " + avg); long add = 0; long minus = 0; // long add2 = 0; // long minus2 = 0; if (del == 0) { for (int i = 1; i < nums.length; i++) { if (nums[i] > avg) { minus += nums[i] - avg; } else { add += avg - nums[i]; } // if (nums[i] > avg2) { // minus2 += nums[i] - avg2; // } else { // add2 += avg2 - nums[i]; // } } } else { for (int i = 0; i < nums.length - 1; i++) { if (nums[i] > avg) { minus += nums[i] - avg; } else { add += avg - nums[i]; } // if (nums[i] > avg2) { // minus2 += nums[i] - avg2; // } else { // add2 += avg2 - nums[i]; // } } } // return Math.min(Math.max(add, minus), Math.max(add2, minus2)); return Math.max(add, minus); } }
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); long sum = 0; long[] a = new long[n]; for (int i = 0; i < n; ++i) { a[i] = in.nextLong(); sum += a[i]; } Arrays.sort(a); if (sum % n == 0) { long avg = sum / n; System.out.println(cp(a, avg)); } else { // 将最大值作为垃圾数 long s = sum - a[n - 1]; long[] t = new long[n - 1]; System.arraycopy(a, 0, t, 0, n - 1); long ans1 = cp(t, s / (n - 1)); long ans2 = cp(t, s / (n - 1) + 1); // 将最小值作为垃圾数 s = sum - a[0]; System.arraycopy(a, 1, t, 0, n - 1); long ans3 = cp(t, s / (n - 1)); long ans4 = cp(t, s / (n - 1) + 1); long ans = Math.min(Math.min(ans1, ans2), Math.min(ans3, ans4)); System.out.println(ans); } } static long cp(long[] a, long avg) { long ans1 = 0, ans2 = 0; for (long x: a) { if (x > avg) ans1 += x - avg; else ans2 += avg - x; } return Math.max(ans1, ans2); } }
package zhongShuCaoZuoShu; import java.util.Arrays; import java.util.Scanner; import static java.lang.Math.abs; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int[] arr = new int[N]; // 和 // 目标众数 // 操作次数 int sum = 0; int target = 0; // int count=0; for(int i =0;i;i++){ arr[i]=in.nextInt(); sum += arr[i]; } // System.out.println(sum); // 一串数据怎么知道会不会出现更多的众数呢 if(arr.length==0 || arr==null){ System.out.print(0); } Arrays.sort(arr); System.out.print(findArr(arr,sum,N)); } public static int findArr(int[] arr,int sum,int N){ int target =sum/N; int count = 0; // 直观上来说,如果一串数据能够都划为众数,说明他们的和能够被位数整除,例如1 4 4,和为9,位3,整除 // 2 3 5 6 --> 4 4 4 4 则16除4位,整除 // 极端情况,一组数据都能划为众数 if(sum%N==0){ // 整除说明全部众数 for(int i = 0;i;i++){ count += abs(target-arr[i]); } count /= 2; // System.out.println(target); }else{ // 如果不能我们就刨除最大或最小的值 int[] newArr = new int[N-1]; if(arr[N-1]-target>target-arr[0]){ // 大的离得更远 // 退掉最高位 for(int i =0;i1;i++){ newArr[i]=arr[i]; } //控制sum值 sum=sum-arr[N-1]; }else{ // 小的离得远 // 退掉小位 for(int i =0;i1;i++){ newArr[i]=arr[i+1]; } //控制sum值 sum=sum-arr[0]; } //让N-1长度减少 N=N-1; findArr(newArr,sum,N); } return count; } }
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int[] arr = new int[N]; // 和 // 目标众数 // 操作次数 int sum = 0; int target = 0; // int count=0; for(int i =0;i<N;i++){ arr[i]=in.nextInt(); sum+=arr[i]; } // System.out.println(sum); // 一串数据怎么知道会不会出现更多的众数呢 if(arr.length==0 || arr==null){ System.out.print(0); } Arrays.sort(arr); System.out.print(findArr(arr,sum,N)); } public static int findArr(int[] arr,int sum,int N){ int target =sum/N; int count = 0; // 直观上来说,如果一串数据能够都划为众数,说明他们的和能够被位数整除,例如1 4 4,和为9,位3,整除 // 2 3 5 6 --> 4 4 4 4 则16除4位,整除 // 极端情况,一组数据都能划为众数 if(sum%N==0){ // 整除说明全部众数 for(int i = 0;i<N/2;i++){ count += target-arr[i]; } // System.out.println(target); }else{ // 如果不能我们就刨除最大或最小的值 int[] newArr = new int[N-1]; if(arr[N-1]-target>target-arr[0]){ // 大的离得更远 // 退掉最高位 for(int i =0;i<N-1;i++){ newArr[i]=arr[i]; } //控制sum值 sum=sum-arr[N-1]; }else{ // 小的离得远 // 退掉小位 for(int i =0;i<N-1;i++){ newArr[i]=arr[i+1]; } //控制sum值 sum=sum-arr[0]; } //让N-1长度减少 N=N-1; findArr(newArr,sum,N); } return count; } }能不能帮哥们看看哪里没考虑到吗
//看完了思路还是写了一小时... #include <iostream> #include <locale> #include<vector> #include<algorithm> #include<climits> using namespace std; typedef long long LL; LL q[100010]; LL method(int l,int r,LL target)//区间[l,r]的众数为target,返回操作次数 { LL res=0; for(int i=l;i<=r;i++) res+=abs(q[i]-target); return res; } int main() { int n; cin>>n; LL sum=0; for(int i=0;i<n;i++) { cin>>q[i]; sum+=q[i]; } if(sum%n==0) { cout<<method(0,n-1,sum/n)/2; return 0; } //如果不能整除,尝试删掉最大值或者最小值 sort(q,q+n); //删掉最大值 LL tmp_sum=sum-q[n-1]; LL target=tmp_sum/(n-1); LL max_res_1=method(0,n-2,target)+abs(tmp_sum-(n-1)*target); LL max_res_2=method(0,n-2,target+1)+abs(tmp_sum-(n-1)*(target+1)); LL max_res=min(max_res_1,max_res_2); //删掉最小值 tmp_sum=sum-q[0];target=tmp_sum/(n-1); LL min_res_1=method(1,n-1,target)+abs(tmp_sum-(n-1)*target); LL min_res_2=method(1,n-1,target+1)+abs(tmp_sum-(n-1)*(target+1)); LL min_res=min(min_res_1,min_res_2); cout<<min(min_res,max_res)/2; return 0; } // 64 位输出请用 printf("%lld")