学步园

http://acm.fzu.edu.cn/problem.php?pid=1914

这是"2010年全国大学生程序设计邀请赛（福州）"的F题,

当时卡这题很久, 一直没有AC....

今天上foj, 看到把题目挂出来了.

继续做, 一次就AC了,

哎, rp啊........很无语

如果当时能冷静点, 如果当时思路在开放点.....如果......如果........

/***************************************************/

1<= n <= 500000这么大的数据, 暴力是铁定tle的,

肯定每个人都知道要有线性算法才性.

我的思路是:

变量total表示所有符合条件的系列, 开始total=n;

从后往前扫描, 遇到负数就向前累加total--且flag[i]=1(表示已被访问过) , 直到和为正数为止. 

这样遍历完整个数组,

如果到遍历完后累加和sum<=0, 则将sum再从数组最后开始累加直到和为正, 此时, 如果flag[i]=0则total--;

代码:

#include<iostream><br /> using namespace std;<br /> __int64 a[500001];<br /> bool flag[500001];<br /> int main()<br /> {<br /> int t,n,i,total,id=1;<br /> __int64 sum;<br /> scanf("%d",&t);<br /> while(t--)<br /> {<br /> scanf("%d",&n);<br /> memset(flag,0,sizeof(bool)*(n+1));<br /> total=n;<br /> for(i=0;i<n;i++)<br /> scanf("%I64d",&a[i]);<br /> sum=a[n-1];<br /> if(sum<=0)<br /> {<br /> total--;<br /> flag[n-1]=1;<br /> }<br /> for(i=n-2;i>=0;i--)<br /> {<br /> if(sum<=0)<br /> {<br /> sum+=a[i];<br /> if(sum<=0)<br /> {<br /> total--;<br /> flag[i]=1;<br /> }<br /> }<br /> else<br /> {<br /> if(a[i]<=0)<br /> {<br /> sum=a[i];<br /> total--;<br /> flag[i]=1;<br /> }<br /> }<br /> }<br /> if(sum<=0)<br /> {<br /> for(i=n-1;i>=0;i--)<br /> {<br /> sum+=a[i];<br /> if(sum<=0 && flag[i]==0)<br /> total--;<br /> if(sum>0)<br /> break;<br /> }<br /> }<br /> printf("Case %d: %d/n",id++,total);<br /> }<br /> return 0;<br /> }