xtu oj 众数

样例输入#

3
1 0
1
2 1
1 2
3 1
1 2 2

样例输出#

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;}
}