第5题 摩天楼(mofa) 时限:1s 空间:256m
有N栋摩天楼,第i栋摩天楼的高度是Hi。FJ有一种魔法,对一栋摩天楼用一次魔法就可以使得该摩天楼的高度加1。同一栋摩天楼可以多次使用魔法。FJ的目标是使得至少有M栋摩天楼的高度是相同的。问至少需要使用多少次魔法?
【输入格式】
多组测试数据。
第一行,一个整数G,表示有G组测试数据。1 <= G <= 5。
每组测试数据格式如下:
第一行,N和M 。 1<= N <= 50。 1 <= M <= N。
第二行,N个整数,第i个整数表示Hi,1 <= Hi <=50
【输出格式】
共G行,每行一个整数。
【输入样例】
3
6 3
1 1 2 2 3 3
3 1
1 2 3
8 5
1 1 1 1 50 50 50 50
【输出样例】
1
0
49
#include <stdio.h>
int main() {
int G=0;
scanf("%d",&G);
int N,M;
int temp=0;
int Hi[51]={0};
for(int i=0;i<G;++i)
{
int step=0;
memset(Hi,0,sizeof(Hi));
scanf("%d %d",&N,&M);
for(int j=0;j<N;++j)
{
scanf("%d",&temp);
++Hi[temp];
}
int max_id=0;
int max = Hi[0];
for(int j=50;j>=1;--j)
{
if(max < Hi[j]){
max = Hi[j];
max_id = j;
}
}
if(Hi[max_id]>=M){
printf("0\n");
continue;
}
int t=1;
while(1){
if(max_id+t<=50 && Hi[max_id+t]>0)
{
if(Hi[max_id+t]+Hi[max_id] > M)
{
printf("%d\n",step+t*(M-Hi[max_id]));
break;
}else{
step = step+t*Hi[max_id+t];
Hi[max_id] += Hi[max_id+t];
Hi[max_id+t]=0;
}
}
if(max_id-t>=0 && Hi[max_id-t]>0)
{
if(Hi[max_id-t]+Hi[max_id] > M)
{
printf("%d\n",step+t*(M-Hi[max_id]));
break;
}else{
step = step+t*Hi[max_id-t];
Hi[max_id] += Hi[max_id-t];
Hi[max_id-t]=0;
}
}
if(max_id+t>50 && max_id-t<0)
break;
++t;
}
}
return 0;
}