频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU-4193 Non-negative Partial Sums单调队列
2012-10-09 11:28:12      个评论      
收藏   我要投稿
题意:给定一个数列,进行绕环移动,然后问所有前缀和都大于等于零的数列有多少。
        首先按照一般方法,把数列往后复制,即a1a2,,,ana1a2,,,an,然后对其求前缀和。接下来就要求移动的区间内的最小值(这里很像POJ2823),看其是否大于等于零。那么就可用到单调队列来求了,队列里保存当前区间里的单调不递减的值,那么就可以在O(1)的复杂度内知道当前区间的最小值,即队首元素大于等于零,则ans+1。
     My code:
[cpp]
//STATUS:C++_AC_703MS_198000KB 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<algorithm> 
#include<string> 
#include<vector> 
#include<queue> 
#include<stack> 
#include<set> 
#define LL __int64 
#define Max(x,y) ((x)>(y)?(x):(y)) 
#define Min(x,y) ((x)<(y)?(x):(y)) 
#define lson l,mid,rt<<1 
#define rson mid+1,r,rt<<1|1 
#define mem(a,b) memset(a,b,sizeof(a)) 
const int MAX=1000010,INF=200000000,MOD=1000000007; 
const double esp=1e-6; 
 
int num[MAX*2],sum[MAX*2],q[MAX*2]; 
int n; 
 
int main() 

//  freopen("in.txt","r",stdin); 
    int i,j,front,rear,ans,max; 
    while(~scanf("%d",&n) && n) 
    { 
        max=(n<<1); 
        ans=front=rear=0; 
        for(i=0;i<n;i++){ 
            scanf("%d",&num[i]); 
            num[n+i]=num[i]; 
        } 
        sum[0]=num[0]; 
        for(i=1;i<max;i++) 
            sum[i]=sum[i-1]+num[i]; 
 
        for(i=0;i<n;i++){ 
            while(rear>front && q[rear-1]>sum[i]) 
                rear--; 
            q[rear++]=sum[i]; 
        } 
        if(q[0]>=0)ans++; 
 
        for(i=0;i<n-1;i++){ 
            if(q[front]==sum[i]) 
                front++; 
            while(rear>front && q[rear-1]>sum[n+i]) 
                rear--; 
            q[rear++]=sum[n+i]; 
            if(q[front]-sum[i]>=0)ans++; 
        } 
 
        printf("%d\n",ans); 
    } 
    return 0; 
点击复制链接 与好友分享!回本站首页
相关TAG标签 队列
上一篇:HUD-4419 Colourful Rectangle 线段树+扫描线+离散
下一篇: UVa 532 - Dungeon Master
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站