学步园

题意很简单，但是数据规模比较大。

第一步的优化就是使用sum数组，sum[i]表示1到i的和。能快速计算其中连续一段数据之和。

显然主要的操作就是对于sum[j] (j>=L),寻找最大的sum[i] ( max(0,j-U)<=i<=j-L)。

虽然很符合RMQ算法，可是我用RMQ还是超时了。。

最后用一个priority_queue解决的。优先级队列满足我们求极值的要求。实现时，我们只需从头扫描队列一次，枚举每个子队列的最后位置。在每个位置处，依次弹出队头，检查下标是否能使子队列的长度在[L,U],如不能就丢弃，直到找到合适的元素(注意不能把该元素也弹出)。每次检查后，把新元素加入队列。

/* source code of submission 339148, Zhongshan University Online Judge System */</p> <p>#include<cstdio><br /> #include<queue><br /> using namespace std;</p> <p>int min( int x, int y)<br /> {<br /> return x<y? x: y;<br /> }</p> <p>struct node<br /> {<br /> int s,no;<br /> node()<br /> {<br /> s=no=0;<br /> }</p> <p> bool operator<(const node &y) const<br /> {<br /> return s<y.s;<br /> }<br /> };</p> <p>int n,l,u,ans;<br /> node sum[33000];<br /> int d[21];<br /> int st[33000][20];</p> <p>int main()<br /> {<br /> int i,j;<br /> while ( scanf("%d",&n) && n!=0 )<br /> {<br /> scanf("%d%d", &l, &u);<br /> sum[0].s=0;<br /> for (i=1; i<=n; ++i)<br /> {<br /> sum[i].no=i;<br /> scanf("%d",&sum[i].s);<br /> sum[i].s+=sum[i-1].s;<br /> }</p> <p> priority_queue<node> q;</p> <p> for (int i=0; i<=l; ++i)<br /> q.push(sum[i]);</p> <p> ans=sum[l].s-sum[0].s;<br /> for (int i=l; i<=n; ++i)<br /> {<br /> node tmp;<br /> while ( true )<br /> {<br /> tmp=q.top();</p> <p> if ( tmp.no<=i-l && tmp.no>=i-u )//长度合适<br /> break;<br /> q.pop();<br /> }<br /> ans= min( ans,sum[i].s-tmp.s);<br /> q.push( sum[i-l+1] );</p> <p> }</p> <p> printf("%d/n", ans);<br /> }</p> <p> return 0;<br /> }