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

· · 题解

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

分析

贪心加数学理论。

思路

普通情况很好算，将三次总和直接除 3 并向上取整即可，因为如果有余数的话，向上取整相当于求出最小分数加 1，这里不考虑令人惊讶的情况，所以最小分数加 1，就是最大分数。如果没有余数，向上取整会取当前整数。

接下来看令人惊讶的情况。这里加特判，如果三次总和小于 2 时，最小分数会小于 0，不能出现分数为负数的情况，所以要加特判。同理，不能出现分数大于 10 的情况，所以三次分数不会大于 28，也要加特判。

我们设最小分数为 x，因为这是令人惊讶的三元组，所以最大分数一定是 x+2，接下来就差中间那个数了。因为中间那个数不能大于最大分数也不能小于最小分数，所以中间数（设为 k）的取值范围为 x≤k≤x+2，所以 k 可取 x，x+1，x+2。

那我们就来分类讨论：

我们需要找到一个式子，使得在三种中间数的取值中都能正确的算出 x+2，观察发现三个式子都可以通过将总和加 2 再除 3 并向上取整算出最大分数 x+2。所以在令人惊讶的三元组中，可以通过将总和加 2 除 3 并向上取整算出最大分数 x+2。

接下来进行判断，我们定义两个变量：一个存储答案数量；一个存储三元组满足原本最大分数不大于等于 p，但成为三元组后最大分数大于等于 p 的三元组数量（这里不能直接将答案数组加一，因为令人惊讶的三元组数量有规定）。

那么如果原本最大分数就大于等于 p 了，直接将答案变量加一。否则再判断，如果它成为令人惊讶的三元组后最大分数大于等于 p，就将预答案数量加一（即将存储满足原本最大分数不大于等于 p，但成为三元组后最大分数大于等于 p 的三元组数量的变量加一）。

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

代码

#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;
}