题解 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