选择两个元素，一个加 1，另一个减 1。
小美希望若干次操作后，众数的出现次数尽可能多。你能帮她求出最小的操作次数吗？
众数定义：在一组数据中，出现次数最多的数据，是一组数据中的原数据，而不是相应的次数。 一组数据中的众数不止一个，如数据2、3、-1、2、1、3中，2、3都出现了两次，它们都是这组数据中的众数。
[编程题]小美的数组操作
- 热度指数：1860 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
小美拿到了一个数组，她每次可以进行如下操作：
选择两个元素，一个加 1，另一个减 1。
选择两个元素，一个加 1，另一个减 1。
输入描述:
第一行为一个正整数，代表数组的大小。
第二行输入，代表小美拿到的数组。
输出描述:
一个整数，代表最小的操作次数。
示例1
输入
3 1 4 4
输出
2
说明
第一次操作：第一个数加 1，第二个数减 1。第二次操作：第一个数加 1，第三个数减 1。数组变成[3,3,3]，众数出现了 3 次。
示例2
输入
3 1 5 5
输出
0
说明
众数出现了 2 次，由于无法再用操作使得众数出现的次数变得更多，所以无需操作。
大体上分两种情况
（1）数组的和（sum），能够整除数组元素的个数（n）。这时，众数就是数组的平均数avg，众数的数量是n。此时计算操作数，那就是每个元素到平均数avg的距离之和除以2，除以二是因为，每一次操作，一个数加一，另一个数减一。因此，计算每个元素到平均数avg的距离之和，相当于把每一次操作算了两遍，后面除以2才是真正的操作数
（2）数组的和（sum），不能整除数组元素的个数（n）。这时，众数的数量是n-1，把数组中的一个数当做垃圾桶（称之为垃圾数），可以把多余的操作都用在垃圾数上，从而让另外n-1个数相同，达到n-1个众数。运用贪心的思想，这个垃圾数一定是数组的最大值或者最小值。
我们以最大值作为垃圾数为例，此时，众数就是剩下n-1个数的平均值（avg），但是有可能不能整除，所以，众数有可能是avg，也有可能是avg+1，（C++默认向下取正）。所以分众数分别是avg和avg+1两种情况讨论，假定众数就是avg，我们现在去计算操作数，定义了两个变量a，b，a用来统计减操作的次数，b用来统计加操作的次数，整体的操作数是max(a,b)，a和b的差值就是用在垃圾数上的操作次数。同理，定义c，d去计算众数是avg+1情况下的操作数。最终取min(max(a,b),max(c,d))为最终的操作数。所以，comp函数可以计算数组l到r元素的操作数。
同理，最小值作为垃圾数的操作数也通过comp函数计算。最终的结果就是最大值作为垃圾数，和最小值作为垃圾数两种情况下的操作数的最小值
（1）数组的和（sum），能够整除数组元素的个数（n）。这时，众数就是数组的平均数avg，众数的数量是n。此时计算操作数，那就是每个元素到平均数avg的距离之和除以2，除以二是因为，每一次操作，一个数加一，另一个数减一。因此，计算每个元素到平均数avg的距离之和，相当于把每一次操作算了两遍，后面除以2才是真正的操作数
（2）数组的和（sum），不能整除数组元素的个数（n）。这时，众数的数量是n-1，把数组中的一个数当做垃圾桶（称之为垃圾数），可以把多余的操作都用在垃圾数上，从而让另外n-1个数相同，达到n-1个众数。运用贪心的思想，这个垃圾数一定是数组的最大值或者最小值。
我们以最大值作为垃圾数为例，此时，众数就是剩下n-1个数的平均值（avg），但是有可能不能整除，所以，众数有可能是avg，也有可能是avg+1，（C++默认向下取正）。所以分众数分别是avg和avg+1两种情况讨论，假定众数就是avg，我们现在去计算操作数，定义了两个变量a，b，a用来统计减操作的次数，b用来统计加操作的次数，整体的操作数是max(a,b)，a和b的差值就是用在垃圾数上的操作次数。同理，定义c，d去计算众数是avg+1情况下的操作数。最终取min(max(a,b),max(c,d))为最终的操作数。所以，comp函数可以计算数组l到r元素的操作数。
同理，最小值作为垃圾数的操作数也通过comp函数计算。最终的结果就是最大值作为垃圾数，和最小值作为垃圾数两种情况下的操作数的最小值
#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")
编辑于 2023-08-25 17:20:57
回复(16)
基于@一叶知秋201910082239620 的思路写的Java版
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
private static long target = -1;
private static List<Integer> remove = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
long sum = 0L;
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
sum += arr[i];
}
// 众数要么是n个，要么是n-1个，
// 能整除就是n个，不能整除就是n-1个，其中的一个数用来接收多余的操作
long ans = 0L;
if (sum % n == 0) {
long target = sum / n;
ans = calOps(arr,target,-1);
} else {
// 基于贪心的思想，排除的数要么是最大，要么是最小，两者取操作数最小的作为结果
Arrays.sort(arr);
ans = Math.min( cal(arr, sum, 0), cal(arr, sum, arr.length - 1));
}
System.out.println(ans);
}
private static long cal(int[] arr, long sum, int excludeIndex) {
long ans = 0L;
sum = sum - arr[excludeIndex];
long target = sum / (arr.length - 1);
// avg = sum(n-1个数) / n-1， avg有可能整除，有可能不整除，因此不整除时还要计算众数为avg+1的操作数，取最小
if( sum % (arr.length -1) == 0){
return calOps(arr,target,excludeIndex);
}else{
return Math.min(calOps(arr,target,excludeIndex),calOps(arr,target+1,excludeIndex));
}
}
/**
* 计算排除了excludeIndex后，其他数变为target所需要的操作数
*/
private static long calOps(int[] arr, long target, int excludeIndex) {
long add = 0L;
long minus = 0L;
for (int i = 0; i < arr.length; i++) {
if (i == excludeIndex) continue;
if (target - arr[i] > 0) {
// 加的操作数
add += target - arr[i];
} else {
// 减的操作数
minus += arr[i] - target;
}
}
// 如果不用排除，则add==minus，
// 否则|add-minus|多余的操作则作用在excludeIndex的数上
return Math.max(add, minus);
}
}
编辑于 2024-01-30 18:52:17
回复(0)
#include <iostream>
#include<map>
#include<climits>
#include<cmath>
using namespace std;
int main() {
/*
思路:
加一减一，貌似意味着有一串数字，如果个数为n且其和能够被n整除，就可以变为n个一样的数
基于此：
1求出所有数的和
2.若和能够被n整除则可假设目标众数为sum/n,求操作次数
若和不能被整除,为保证最小的操作次数，必须将变化最多的数剔除，也就是数组中最大或最小的元素。
目标众数设置为 （sum - （max or min） ） / n - 1 或其+1，具体选择四舍五入;求操作次数
3.操作次数的求法，看数与目标众数的绝对值，大于1点就一次。最后除以2
*/
long long res = 0;
long long sum = 0;
//元素个数
long long n = 0;
cin>>n;
//<数字,次数>
map<long,long> dgCount;
long long maxNum = LONG_MIN;
long long minNum = LONG_MAX;
long long tempNum;
for(long long i = 0; i < n; i++)
{
cin >> tempNum;
//出现次数加一
dgCount[tempNum] += 1;
//求和
sum += tempNum;
if(maxNum < tempNum)
{
maxNum = tempNum;
}
if(minNum > tempNum)
{
minNum = tempNum;
}
}
long long target = 0;
//和能够被n整除的情况
if (sum % n == 0) {
target = sum / n;
for(auto it:dgCount)
{
res += abs(it.first-target)*it.second;
}
cout<< res / 2;
return 0;
}
//假定最大数需要最多操作次数
long long maxRes = 0;
//剔除一个最大数
dgCount[maxNum] --;
//开始计算目标众数
target = round((sum - maxNum) / ((n-1)*1.0));
//求操作次数
for(auto it:dgCount)
{
maxRes += abs(it.first-target)*it.second;
}
//最终答案需要除以2,将多余变化再加一次
maxRes += abs(sum - maxNum - target * (n-1));
//恢复
dgCount[maxNum]++;
long long minRes = 0;
dgCount[minNum] --;
target = round((sum - minNum) / ((n-1)*1.0));
for(auto it:dgCount)
{
minRes += abs(it.first-target)*it.second;
}
minRes += abs(sum - minNum - target * (n-1));
cout<< (minRes<maxRes?minRes:maxRes)/2;
return 0;
}
// 64 位输出请用 printf("%lld")
#include<map>
#include<climits>
#include<cmath>
using namespace std;
int main() {
/*
思路:
加一减一，貌似意味着有一串数字，如果个数为n且其和能够被n整除，就可以变为n个一样的数
基于此：
1求出所有数的和
2.若和能够被n整除则可假设目标众数为sum/n,求操作次数
若和不能被整除,为保证最小的操作次数，必须将变化最多的数剔除，也就是数组中最大或最小的元素。
目标众数设置为 （sum - （max or min） ） / n - 1 或其+1，具体选择四舍五入;求操作次数
3.操作次数的求法，看数与目标众数的绝对值，大于1点就一次。最后除以2
*/
long long res = 0;
long long sum = 0;
//元素个数
long long n = 0;
cin>>n;
//<数字,次数>
map<long,long> dgCount;
long long maxNum = LONG_MIN;
long long minNum = LONG_MAX;
long long tempNum;
for(long long i = 0; i < n; i++)
{
cin >> tempNum;
//出现次数加一
dgCount[tempNum] += 1;
//求和
sum += tempNum;
if(maxNum < tempNum)
{
maxNum = tempNum;
}
if(minNum > tempNum)
{
minNum = tempNum;
}
}
long long target = 0;
//和能够被n整除的情况
if (sum % n == 0) {
target = sum / n;
for(auto it:dgCount)
{
res += abs(it.first-target)*it.second;
}
cout<< res / 2;
return 0;
}
//假定最大数需要最多操作次数
long long maxRes = 0;
//剔除一个最大数
dgCount[maxNum] --;
//开始计算目标众数
target = round((sum - maxNum) / ((n-1)*1.0));
//求操作次数
for(auto it:dgCount)
{
maxRes += abs(it.first-target)*it.second;
}
//最终答案需要除以2,将多余变化再加一次
maxRes += abs(sum - maxNum - target * (n-1));
//恢复
dgCount[maxNum]++;
long long minRes = 0;
dgCount[minNum] --;
target = round((sum - minNum) / ((n-1)*1.0));
for(auto it:dgCount)
{
minRes += abs(it.first-target)*it.second;
}
minRes += abs(sum - minNum - target * (n-1));
cout<< (minRes<maxRes?minRes:maxRes)/2;
return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2023-08-31 12:04:27
回复(0)
天呐 天呐 这道题卡了我一天，终于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));
}
发表于 2023-10-07 22:33:48
回复(0)
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))
发表于 2023-10-08 22:40:28
回复(0)
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);
}
}
发表于 2024-09-01 17:28:59
回复(0)
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);
}
}
发表于 2024-04-13 09:44:11
回复(0)
参考评论第一的思路。
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);
}
}
编辑于 2023-12-26 20:56:48
回复(0)
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; }
}
发表于 2023-10-06 20:50:55
回复(0)
from itertools import accumulate
n = int(input())
a = [int(c) for c in input().split()]
a.sort()
sum_ = sum(a)
if sum_ % n == 0:
res = 0
avg = sum_ // n
for i in a:
res += abs(avg - i)
res //= 2
print(res)
else:
nums1 = a[1:]
nums2 = a[:-1]
def cal(nums):
sum_ = sum(nums)
avg = int(sum_ / len(nums) + 0.5)
x,y = 0, 0
for num in nums:
if num >= avg: x+= num -avg
else: y+= avg - num
return max(x,y)
print(min(cal(nums1), cal(nums2)))
发表于 2023-09-24 20:56:06
回复(0)
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;
}
}
能不能帮哥们看看哪里没考虑到吗
发表于 2023-09-07 17:35:02
回复(1)
//看完了思路还是写了一小时...
#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")
发表于 2023-09-07 15:42:00
回复(0)
用Python做的，27/30的通过率，来个大佬看看哪出问题了
whileTrue:
try:
sum = 0
ave = 0
ave1 = 0
ave2 = 0
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
fori in range(n):
sum += a[i]
ifsum % n == 0:
fori in range(n):
ave += abs(sum / n - a[i])
print(int(ave / 2))
elif sum - a[0] * n > a[-1] * n - sum:
sum -= a[0]
ifsum / (n - 1) - sum // (n - 1) > 0.5:
med = sum // (n - 1) + 1
else:
med = sum // (n - 1)
fori in range(n - 1):
ifa[i + 1] < med:
ans1 = med - a[i + 1]
ave1 += ans1
else:
ans2 = a[i + 1] - med
ave2 += ans2
print(int(((ave1 + ave2)-abs(ave1 - ave2)) / 2+ abs(ave1 - ave2)))
else:
sum -= a[-1]
ifsum / (n - 1) - sum // (n - 1) > 0.5:
med = sum // (n - 1) + 1
else:
med = sum // (n - 1)
fori in range(n - 1):
ifa[i] < med:
ans1 = med - a[i]
ave1 += ans1
else:
ans2 = a[i] - med
ave2 += ans2
print(int(((ave1 + ave2)-abs(ave1 - ave2)) / 2+ abs(ave1 - ave2)))
except:
break
发表于 2023-09-06 23:53:32
回复(0)
#include <stdio.h>
#include <stdlib.h>
static int cmp_int(const void *p1, const void *p2)
{
return *(long *)p1 - *(long *)p2;
}
// long max_num = 0, min_num = __INT64_MAX__;
long find_cnt(long *nums, int size, long avg, int flag)
{
long cnt_add = 0;
long cnt_delete = 0;
for (int i = 0; i < size; i++)
{
if (nums[i] < avg) {
cnt_add += avg - nums[i];
} else if (nums[i] > avg) {
cnt_delete += nums[i] - avg;
}
}
if (flag == 1) {
if (cnt_add > cnt_delete) {
cnt_add -= (avg - nums[0]);
} else {
cnt_delete -= (nums[size - 1] - avg);
}
}
return cnt_add > cnt_delete? cnt_add: cnt_delete;
}
int main(int argc, char *argv[])
{
int size = 0;
scanf("%d", &size);
long nums[size];
long sum = 0;
for (int i = 0; i < size; i++)
{
scanf("%ld", &nums[i]);
sum += nums[i];
// if (nums[i] < min_num) {
// min_num = nums[i];
// }
// if (nums[i] > max_num) {
// max_num = nums[i];
// }
}
qsort(nums, size, sizeof(long), cmp_int);
long result = 0;
if (sum % size == 0) {
result = find_cnt(nums, size, sum / size, 0);
} else {
long select_nums[4];
select_nums[0] = (sum - nums[0]) / (size - 1);
select_nums[1] = select_nums[0] + 1;
select_nums[2] = (sum - nums[size - 1]) / (size - 1);
select_nums[3] = select_nums[2] + 1;
long tmp = 0;
result = find_cnt(nums, size, select_nums[0], 1);
for (int i = 1; i < 4; i++)
{
tmp = find_cnt(nums, size, select_nums[i], 1);
if (tmp < result) {
result = tmp;
}
}
}
printf("%ld\r\n", result);
return 0;
}
发表于 2023-08-29 15:24:11
回复(0)
问题信息
相关试题
-
评论(9) 来自2023年美团秋招编程岗...
-
评论(20) 来自2023年美团秋招编程岗...
-
评论(18) 来自2023年美团秋招编程岗...
-
评论(10) 来自2023年美团秋招编程岗...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
