如何创作网站,网站更换内容,昆山网页设计报价,不良广告样例输入#
3
1 0
1
2 1
1 2
3 1
1 2 2样例输出#
1
2
3
解题思路#xff1a;与数组大小有关#xff0c;先排序
举个例子思考一下
n4 k2 数组为1 2 3 4
如果我们想让众数那个位的值为3(即max3)#xff0c;3出现的次数为3#xff0c;即众数为3#xff0c;需要修改多少次…
样例输入#
3
1 0
1
2 1
1 2
3 1
1 2 2样例输出#
1
2
3
解题思路与数组大小有关先排序
举个例子思考一下
n4 k2 数组为1 2 3 4
如果我们想让众数那个位的值为3(即max3)3出现的次数为3即众数为3需要修改多少次
答案是3-13-23-33次
不妨利用前缀和来计算。
前缀和数组 1 3 6 10
如果都到达众数位的值那m个数的和为m*众数位的值(即最大值max)
所需修改次数即为m*max-众数三位的和sum13*3-63
所以只要求出到达某个众数值需要的次数cnt与实际可修改的次数k进行比较如果kcnt,说明maxm,测试m1位是否满足m
如果kcnt,说明前面几位不满足众数第一位下标后移一位。
具体实现看代码。
#includestdio.h
#includestdlib.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(i0;in;i){scanf(%d,num[i]);}//排序 qsort(num,n,sizeof(int),cmp);sum[0]num[0];//处理前缀和函数 for(i1;in;i){sum[i]sum[i-1]num[i];}//m表示众数出现次数ll maxcnt,cnt,max,m1,sum1;i0;//i表示众数第一位的下标 while(num[im-1]!\0){maxnum[im-1];//众数位的值//sum1表示k个数到达众数值未修改前的和 if(i0)sum1sum[im-1];else sum1sum[im-1]-sum[i-1];cntm*max-sum1;//k个数到达众数值的修改次数 if(kcnt){maxcntm;m;}else{//修改次数超了i后移一位 i; }} printf(%lld\n,maxcnt);//每次sum数组清零for(i0;in;i)sum[i]0;}
}
