题解 P2777 【[AHOI2016初中组]自行车比赛】

· · 题解

啊这是我的第一篇题解

在机房刷精选题库的时候找到了这道称心如意的黄题

(也是我人生第一道黄题,生动形象地写出了我的蒻)

好吧不扯了步入正题

初读题的时候是没什么的,挺有自信能AC

当时的思路是这样的:

从极端状况考虑,循环到的选手积分得第一名,然后目前积分最多的选手(如果不是同一个人)得最后一名,可得:

循环到的选手得分(原得分+N)

积分最多的选手得分(原得分+1)

相互比较,如果循环到的选手最终得分比目前积分最多的选手最终得分多,那这个选手不就有可能是第一了吗?!

于是我码出了代码 边码边想:普及题怎么这么水?

再仔细审题+看样例 发现不大对劲:

样例2输入的数据 12满足我上面的分析但是好像没有算?

自己深搜了一下发现还真是那么回事……

那也就是说我不能用上面分析的简单粗暴的办法水掉这一题?

然后我心态就崩了emm这样如果不行的话我实在想不出来该怎么搞,难道要深搜?估计一个一个深搜得爆TLE吧

有神犇推荐我用贪心,可是本蒟蒻不会用……于是我打算先把模板打出来然后交上去,看看能不能水一两个测试点什么的

#include<stdio.h>
using namespace std;
int main(){
    int n,b[300000],max=0,ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);
        if(b[i]>max)
            max=b[i];
    }
    for(int j=0;j<n;j++){
        if(b[j]+n>=max+1)
            ans++;
    }
    printf("%d",ans);
    return 0;
}

这就是按照我上面的思路构建的模板了,确实……恩

交上去了,页面跳转到waiting,我看着20个测试点心态崩了

纵使我能水到一两个,那也只有十分,这十分有什么用?

然后……judging了……然鹅突然有几个AC蹦了出来,我心里一动

最后20个测试点都AC了……woc这测试点还能再水一点吗……

好吧这道题就这么侥幸地过了,但是我贪心还是得去弄清楚,毕竟逃得过初一逃不过十五……

那就这样了,蒟蒻第一次发题解,有什么做得不好请各位神犇多多指教,下篇题解再见233