xtu oj 众数-样例输出#

1
2
3

解题思路：与数组大小有关，先排序

举个例子思考一下

n=4 k=2 数组为1 2 3 4

如果我们想让众数那个位的值为3(即max=3)，3出现的次数为3，即众数为3，需要修改多少次？

答案是（3-1）+（3-2）+（3-3）=3次

不妨利用前缀和来计算。

前缀和数组 1 3 6 10

如果都到达众数位的值，那m个数的和为m*众数位的值(即最大值max)，

所需修改次数即为m*max-众数三位的和sum1=3*3-6=3

所以，只要求出到达某个众数值需要的次数cnt与实际可修改的次数k进行比较，如果k>=cnt,说明max=m,测试m+1位是否满足，m++

如果k<cnt,说明前面几位不满足，众数第一位下标后移一位。

具体实现看代码。

#include<stdio.h>
#include<stdlib.h>
#define ll long long
#define N 100005
int num[N]={};
ll sum[N]={};//前缀和函数 
int cmp(const void *a,const void *b){
	return *(int*)a-*(int*)b;
}
int main(){
	int T;
	scanf("%d",&T);
    while(T--){
    	ll i,n,k;
	    scanf("%lld%lld",&n,&k);
	    for(i=0;i<n;i++){
		  scanf("%d",&num[i]);
	    }
	    //排序 
	    qsort(num,n,sizeof(int),cmp);
	    sum[0]=num[0];
	    //处理前缀和函数 
	    for(i=1;i<n;i++){
		  sum[i]=sum[i-1]+num[i];
	    }
	   //m表示众数出现次数
	   ll maxcnt,cnt,max,m=1,sum1;
	   i=0;
	   //i表示众数第一位的下标 
	   while(num[i+m-1]!='\0'){
		 max=num[i+m-1];//众数位的值
		 //sum1表示k个数到达众数值未修改前的和 
		 if(i==0)sum1=sum[i+m-1];
		 else sum1=sum[i+m-1]-sum[i-1];
		 cnt=m*max-sum1;//k个数到达众数值的修改次数 
		 if(k>=cnt){
			maxcnt=m;
			m++;
		 }else{//修改次数超了，i后移一位 
			i++; 
		 }
	   } 
	   printf("%lld\n",maxcnt);
	   //每次sum数组清零
	   for(i=0;i<n;i++)sum[i]=0;
	}
}