Sicily 1800. Sequence

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

第一步的优化就是使用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 */


#include<cstdio>
#include<queue>
using namespace std;

int min( int x, int y)
{
    return x<y? x: y;
}


struct node
{
    int s,no;
    node()
    {
        s=no=0;
    }

    bool operator<(const node &y) const
    {
        return s<y.s;
    }
};


int n,l,u,ans;
node sum[33000];
int d[21];
int st[33000][20];

int main()
{
    int i,j;
    while (  scanf("%d",&n) && n!=0 )
    {
        scanf("%d%d", &l, &u);
        sum[0].s=0;
        for (i=1; i<=n; ++i)
        { 
            sum[i].no=i;
            scanf("%d",&sum[i].s);
            sum[i].s+=sum[i-1].s;
        }
        
        priority_queue<node> q;

        for (int i=0; i<=l; ++i)
            q.push(sum[i]);
        
        ans=sum[l].s-sum[0].s;
        for (int i=l; i<=n; ++i)
        {
            node tmp;
            while ( true )
            {
                tmp=q.top();
  
                if ( tmp.no<=i-l && tmp.no>=i-u )//长度合适
                    break;
                q.pop();
            }
            ans= min( ans,sum[i].s-tmp.s);
            q.push( sum[i-l+1] );
            
        }


        printf("%d/n", ans);
    }

    return 0;
}