刚开始看这道题的时候,心想,不就是一个尺取嘛,水题一道,结果如下图:
可以说是大型打脸现场,个人感觉这也和题目给的样例有一点关系(样例似乎太弱了,啥都能跑)(不想承认是自己太菜的事实)
于是乎决定写下我人生中第一篇博客纪念一下
首先附上第一版代码(全是bug):
#include<iostream> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int a[100000+10]={0}; int asum[100000+10]={0}; int sumer=0; int maxer=-INF; int main() { int N,sum=0; cin>>N; for(int i=1;i<=N;i++) { cin>>a[i]; sum+=a[i]; } double ave=sum/2.0; for(int i=1;i<=N;i++) { asum[i]=asum[i-1]+a[i]; } int left=1,right=2; for( ; ; ) { sumer=asum[right]-asum[left]; if(sumer==ave) { cout<<sumer; break; } if(sumer<ave) { maxer=max(maxer,sumer); right++; } if(sumer>ave) { maxer=max(maxer,sum-sumer); left++; } if(left==N) { cout<<maxer; break; } } return 0; }
这个代码是40分段错误,很容易就能发现是我没有处理好right大于N后的情况
于是乎我自作主张将大于N的情况全部定为right=N,这样便得到了第二版40分运行超时的代码
于是我开始思考自己超时的原因,因为要求和,所以我条件反射地想到了前缀和,但是这道题似乎可以不用前缀和
于是我换了一种写法:(这种写法只有60分,报段错误)
#include<iostream> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int a[100000+10]={0}; int sumer=0; int maxer=-INF; int main() { int N,sum=0; cin>>N; for(int i=1;i<=N;i++) { cin>>a[i]; sum+=a[i]; } double ave=sum/2.0; int left=1,right=2; sumer=a[right]+a[left]; for( ; ; ) { if(sumer==ave) { cout<<sumer; break; } if(sumer>ave) { maxer=max(maxer,sum-sumer); left++; sumer-=a[left-1]; } if(sumer<ave) { maxer=max(maxer,sumer); right++; sumer+=a[right]; } if(left==N) { cout<<maxer; break; } } return 0; }
这时候我才意识到自己处理right>N的做法有些粗暴,不应该把它笼统的归为right=N,于是我把这一段改为:
if(right>N) { right=right%N; }
得到了80分的代码
然后我把代码的顺序做了一下微调:
本来是这样的:
if(sumer<ave) { maxer=max(maxer,sumer); right++; sumer+=a[right]; } if(right>N) { right=right%N; }
我把它变成了这样:
if(sumer<ave) { maxer=max(maxer,sumer); right++; if(right>N) { right=right%N; } sumer+=a[right]; }
这也很容易理解,我之前没有考虑周全,其实和自己当时的心态也有一点关系,反正自己交题嘛,随便试,此时的代码是90分,然后我思索了一下觉得唯一的可能就是自己有一些细节没有考虑全面,当时我以为是需要特判,然后把过程又过了一遍,觉得后面的思路应该没问题,这时我才突然发现自己脑瘫,把初始点弄错了
附上AC代码:
#include<iostream> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int a[100000+10]={0}; int sumer=0; int maxer=-INF; int main() { int N,sum=0; cin>>N; for(int i=1;i<=N;i++) { cin>>a[i]; sum+=a[i]; } double ave=sum/2.0; int left=1,right=1; sumer=a[1]; for( ; ; ) { if(sumer==ave) { cout<<sumer; break; } if(sumer>ave) { maxer=max(maxer,sum-sumer); left++; sumer-=a[left-1]; } if(sumer<ave) { maxer=max(maxer,sumer); right++; if(right>N) { right=right%N; } sumer+=a[right]; } if(left==N) { cout<<maxer; break; } } return 0; }
怎么说呢,萌新刚刚开始学习算法,各方面考虑的都不是很周到,这道题算是比较曲折的一道题,明明感觉不难,就是各种细节没考虑清楚,感觉也和自己放松的心态有点关系,所以写下人生中第一道题解(来自蒟蒻的题解)
算是一次留念吧,希望后面学习过程中认真一点,别像这次这么蠢(心情复杂)