与谷歌人共舞（C语言代码）

原题链接：题目494 - ACM在线评测系统

描述：你在观看一场谷歌人（谷歌的雇员）的舞蹈秀。每个舞者被三位评委给出三元组的分数。每三个分数由从0到10的三个整数组成。评委们有非常相似的评价标准，所以让人惊讶的是三元组的分数中是否包含两个分数相差为2。没有三元组包含相差多于2的分数。例如：(8,8,8)和(7,8,7)很一般（不令人惊讶）。(6,7,8)和(6,8,8)是特殊（令人惊讶）的。(7,6,9)则从未出现。每个谷歌人的“总分”就是三元组的分数中每三个数的和。对某个谷歌人来说，“最好结果”是三元组每三个数中的最大值。给出各个谷歌人的“总分”，以及特殊（令人惊讶）三元组的数量，若有些谷歌人曾有过至少为p的“最好结果”，这些谷歌人的最大数（目）是多少？例如：假使有6位谷歌人，他们有了这样一些“总分”：29，20，8，18，18，21。你记着：有2个三元组是特殊（令人惊讶）的，并且你要知道：多少谷歌人曾得到大于或等于8的“最好结果”。有了这些“总分”，并且得知六个三元组中有两个是令人惊讶的，这些三元组表示的分数已能得出：

10 9 10
6 6 8(*)
2 3 3
6 6 6
6 6 6
6 7 8(*)

标记了一个(*)是特殊（令人惊讶）情况。这里给了我们3个谷歌人：他们得到了至少一个8分或更高分。没有哪些三元组系列会给我们一个比3更大的数目，所以答案是3。

输入：输入中的第一行给出了测试用例的数量T。紧跟着T个测试用例。每个测试用例由一单独行构成，行内有被空格分隔的若干整数。第一个整数将成为N，N是谷歌人的数目；第二个整数将成为S，S是特殊（令人惊讶）三元组的数量；第三个整数将成为p，如上所述。接下来的将成为N个整数ti（从t1到tn）：ti是第i个谷歌人的“总分”。限制：1<=T<=100. 1<=N<=100. 0<=S<=N. 0<=p<=10. 0<=ti<=30.。如果“总分”ti中有特殊（令人惊讶）分差（至少有S个这样的总分），ti的范围是[2,28]。

输出：对于每个测试用例，输出一行，包括“Case #x:y”，这里x是用例数（从1开始），y是这样一些谷歌人的数目：在三元组中的分数上获得过大于等于p的“最好结果”。

样例输入：

4
3 1 5 15 13 11
3 0 8 23 22 21
2 1 1 8 0
6 2 8 29 20 8 18 18 21

样例输出：

Case #1: 3
Case #2: 2
Case #3: 1
Case #4: 3

解题思路：与题目来源有关的代码：Google Code Jam 2012 Qualification Round。

分区间讨论“总分”所在的范围：当p>0，在特殊情况下，ti属于[p*3-4,p*3-3]（当p=2时区间为[2,3]，当p=10时区间为[26,27]）；在一般情况下，ti属于[p*3-2,30]。

注意事项：如果p等于0，每个谷歌人都有大于等于0的得分。

参考代码：

#include<stdio.h>
int main(){
	int i,j,c,T,n,s,p,t[100];
	scanf("%d",&T);//输入测试用例的个数
	for(j=1;j<=T;j++){
		scanf("%d%d%d",&n,&s,&p);//n个谷歌人，s个特殊三元组（有两个评分差距为2）
		c=0;//c个谷歌人的三元组评分中，有大于等于p的得分
		for(i=0;i<n;i++){
			scanf("%d",t+i);//输入第i个谷歌人的“总分”
			if(p){//某个谷歌人也许有大于等于p的得分
				if(t[i]){//前提是这个谷歌人的“总分”大于0
					if(t[i]>=p*3-2) c++;//一般情况下三个评分至少为(p-1,p-1,p)，“总分”至少为p*3-2
					//排除任何两评分相差大于2的情况，
					//假如(p-1,p-1,p)中的任何一个低分少1，并且至少有一个高分仍等于p
					//评分经升序排序后可以分别不小于(p-2,p-2,p)，分别不大于(p-2,p-1,p)
					if(t[i]>=p*3-4&&t[i]<=p*3-3&&s){//那么“总分”所在的区间为[p*3-4,p*3-3]
						c++;
						s--;//第i个谷歌人由于低分与高分的差距，属于某个已统计的特殊情况
					}
				}
			}else c++;//每个谷歌人都有大于等于0的得分
		}
		printf("Case #%d: %d\n",j,c);
	}
	return 0;
}