题目描述
韩信点兵，多多益善。
战前，萧何备军。韩信检阅，曰：“增1人？”。萧何答：“甚好”。韩信再曰：“使看齐？”。
萧何再答“甚好”。
输入
输入有多组(不超过100)测试实例。
每组测试实例第1行为1个正整数M(1 ≤ M ≤ 100)，表示接下来有M行士兵的信息。每行士兵信息为两个正整数H(100 <= H <= 200),N(1 <= N <= 1000)，分别表示士兵身高和其对应的士兵人数。
输入结束将由一行M=0的测试实例表示，不应处理此测试实例。
输出
每组测试实例输出一行，格式为：“Case i: sum”，其中i是测试实例的编号(从1开始)，sum为一个正整数，即增加的这名士兵与其他每名士兵的身高差之和，该和满足：是所有可能的和当中最小的和。
样例输入
2
160 1
170 1
4
160 1
165 1
170 1
180 2
0
样例输出
Case 1: 10
Case 2: 35
解析：题目其实就是求插入一个士兵，使得他与每个士兵的身高和达到最小时的，身高差总和。
其实，n个数中，求一个数到所有数差和最小，这个数就是这一列数的中位数，然后再求差和即可。
当然我们其实也可以直接暴力遍历，这题不会超时，但我们得知道，这个插入的士兵的身高数值肯定在原有士兵最矮和最高之间。我们可以利用一个数组来存储原有所有士兵的身高数据，然后遍历求最小值。在这里建议数组开大一点。
中位数：
#include <bits/stdc++.h>
using namespace std;
int k[100005];
int main()
{
int m,n,i,s,mid,cnt=0,sg,ge,sum;
while(~scanf("%d",&n)){ //n种身高的士兵
if(n==0) break;
m=0,sum=0,cnt++; //cnt用来计数case
for(i=0;i<n;i++){
scanf("%d %d",&sg,&ge); //输入身高和对应个数
for(s=0;s<ge;s++) k[m++]=sg; //存入数组
}
sort(k,k+m); //排序
if(m%2==1) mid=k[m/2]; //求出中位数mid
else mid=k[m/2-1];
for(i=0;i<m;i++){
sum=sum+abs(k[i]-mid); //累加
}
printf("Case %d: %d\n",cnt,sum);
}
return 0;
}暴力：
#include <>
int k[1000005];
int main()
{
long long n,i,s,m=0,a,b,max=100,min=200,sum=0,cnt=1,min1=9999999;
while(~scanf("%lld",&n)){
m=0;
if(n==0){
break;
}
for(i=0;i<n;i++){
scanf("%lld %lld",&a,&b);
if(a>max) max=a;
if(a<min) min=a;
for(s=0;s<b;s++){
k[m]=a; //存入k数组中
m++;
}
}
for(i=min;i<=max;i++){
for(s=0;s<m;s++){
sum=sum+abs(i-k[s]); //求身高差和
}
if(sum<min1) min1=sum; //如比最小值小，替换
sum=0;
}
printf("Case %lld: %lld\n",cnt,min1);
cnt++,min1=9999999; //初始化数据，cnt不用，记录第几个测试用例
max=100,min=200;
}
return 0;
}