看到题解区的题解都很复杂、绕口，于是想写一篇大家都能看懂的题解。

分析

贪心加数学理论。

思路

普通情况很好算，将三次总和直接除

3

并向上取整即可，因为如果有余数的话，向上取整相当于求出最小分数加

1

，这里不考虑令人惊讶的情况，所以最小分数加

1

，就是最大分数。如果没有余数，向上取整会取当前整数。

接下来看令人惊讶的情况。这里加特判，如果三次总和小于

2

时，最小分数会小于

0

，不能出现分数为负数的情况，所以要加特判。同理，不能出现分数大于

10

的情况，所以三次分数不会大于

28

，也要加特判。

我们设最小分数为

x

，因为这是令人惊讶的三元组，所以最大分数一定是

x+2

，接下来就差中间那个数了。因为中间那个数不能大于最大分数也不能小于最小分数，所以中间数（设为

k

）的取值范围为

x≤k≤x+2

，所以

k

可取

x

，

x+1

，

x+2

。

那我们就来分类讨论：

若 $k=x$ ，则三数总和为 $x+x+x+2=3x+2$ ，这里求出最大分数 $x+2$ 可以选择将总和先加 $4$ 再除 $3$ ，或者将总和加 $2$ 或 $3$ 向上取整都能求出最大分数 $x+2$ 。
若 $k=x+1$ ，则三数总和为 $x+x+x+2+1=3x+3$ ，这里求出最大分数 $x+2$ 可以选择将总和先加 $3$ 再除 $3$ ，或者将总和加 $1$ 或 $2$ 向上取整都能求出最大分数 $x+2$ 。
若 $k=x+2$ ，则三数总和为 $x+x+x+2+2=3x+4$ ，这里求出最大分数 $x+2$ 可以选择将总和先加 $2$ 再除 $3$ ，或者将总和加 $1$ 向上取整都能求出最大分数 $x+2$ 。

我们需要找到一个式子，使得在三种中间数的取值中都能正确的算出

x+2

，观察发现三个式子都可以通过将总和加

2

再除

3

并向上取整算出最大分数

x+2

。所以在令人惊讶的三元组中，可以通过将总和加

2

除

3

并向上取整算出最大分数

x+2

。

接下来进行判断，我们定义两个变量：一个存储答案数量；一个存储三元组满足原本最大分数不大于等于

p

，但成为三元组后最大分数大于等于

p

的三元组数量（这里不能直接将答案数组加一，因为令人惊讶的三元组数量有规定）。

那么如果原本最大分数就大于等于

p

了，直接将答案变量加一。否则再判断，如果它成为令人惊讶的三元组后最大分数大于等于

p

，就将预答案数量加一（即将存储满足原本最大分数不大于等于

p

，但成为三元组后最大分数大于等于

p

的三元组数量的变量加一）。

接下来再进行判断，如果预答案数量大于等于规定的令人惊讶的三元组数量，就将答案变量增加题目规定的令人惊讶的三元组数量。否则就将答案变量增加预答案数量。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int a[110000];
int main(){
	int t;
	cin>>t;
	for(int rt=1;rt<=t;rt++){
		int n,s,p;
		cin>>n>>s>>p;
		int ans=0,sum=0;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++){
			int h;
			if(a[i]==0||a[i]==1||a[i]==29||a[i]==30){
				if(ceil(1.00*a[i]/3)>=p)sum++;
			}
			else if(ceil(1.00*a[i]/3)>=p){
				sum++;
			}
			else {
				
				h=ceil((2+1.00*a[i])/3);
				if(h>=p)ans++;
			}
		}
		if(ans>=s)sum+=s;
		else sum+=ans;
		cout<<"Case #"<<rt<<": "<<sum<<endl;
	}
	return 0;
}

题解：P13312 [GCJ 2012 Qualification] Dancing With the Googlers

文章操作

分析

思路

代码

相关推荐

评论

题解：P13312 [GCJ 2012 Qualification] Dancing With the Googlers