题目描述
韩信点兵，多多益善。
战前，萧何备军。韩信检阅，曰：“增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 <stdio.h>
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;
}