为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(3)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 259817
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

题目大意:给出一个有N个数字(-1000..1000,N<=10^5)的环状序列,让你求一个和最大的连续子序列。这个连续子序列的长度小于等于K。
分析:因为序列是环状的,所以可以在序列后面复制一段(或者复制前k个数字)。如果用s[i]来表示复制过后的序列的前i个数的和,那么任意一个子序列[i..j]的和就等于s[j]-s[i-1]。对于每一个j,用s[j]减去最小的一个s[i](i>=j-k+1)就可以得到以j为终点长度不大于k的和最大的序列了。将原问题转化为这样一个问题后,就可以用单调队列解决了。

单调队列即保持队列中的元素单调递增(或递减)的这样一个队列,可以从两头删除,只能从队尾插入。单调队列的具体作用在于,由于保持队列中的元素满足单调性,对于上述问题中的每个j,可以用O(1)的时间找到对应的s[i]。(保持队列中的元素单调增的话,队首元素便是所要的元素了)。

维护方法:对于每个j,我们插入s[j-1](为什么不是s[j]? 队列里面维护的是区间开始的下标,j是区间结束的下标),插入时从队尾插入。为了保证队列的单调性,我们从队尾开始删除元素,直到队尾元素比当前需要插入的元素优(本题中是值比待插入元素小,位置比待插入元素靠前,不过后面这一个条件可以不考虑),就将当前元素插入到队尾。之所以可以将之前的队列尾部元素全部删除,是因为它们已经不可能成为最优的元素了,因为当前要插入的元素位置比它们靠前,值比它们小。我们要找的,是满足(i>=j-k+1)的i中最小的s[i],位置越大越可能成为后面的j的最优s[i]。

在插入元素后,从队首开始,将不符合限制条件(i>=j-k+1)的元素全部删除,此时队列一定不为空。(因为刚刚插入了一个一定符合条件的元素)


#include<iostream>
#include
<queue>
using namespace std;
#define INF 0x3fffffff
#define maxn 100010
int num[maxn],sum[maxn];
int main()
{
    
int T;
    
int N,K,n;
    cin
>>T;
    
while(T--)
    {
        cin
>>N>>K;
        sum[
0]=0;
        
for(int i=1;i<=N;i++)
        {
            cin
>>num[i];
            sum[i]
=sum[i-1]+num[i];
        }
        
for(int i=N+1;i<N+K;i++)
        {
            sum[i]
=sum[i-1]+num[i-N];
        }
        n
=N+K-1;
        
        deque
<int> q;
        q.clear();
        
        
int ans=-INF;
        
int start,end;
        
//[j-kj] 枚举以j结尾的区间,找[j-k,j]中sum最小的i
        for(int j=1;j<=n;j++)
        {
            
while(!q.empty() && sum[j-1]<sum[q.back()])
                q.pop_back();
            
while(!q.empty() && q.front()<(j-K))
                q.pop_front();
            q.push_back(j
-1);
            
if(sum[j]-sum[q.front()]>ans)
            {
                ans
=sum[j]-sum[q.front()];
                start
=q.front()+1;
                end
=j;
            }
        }
        cout
<<ans<<" "<<start<<" "<<(end>N?end%N:end)<<endl;
    }
}


posted on 2010-08-04 15:44 baby-fly 阅读(1943) 评论(8)  编辑 收藏 引用 所属分类: Algorithm

Feedback

# re: HDU 3415 单调队列 2010-08-27 19:54 justmeh
不错,单调队列只保存了index,减少了一半的空间。  回复  更多评论
  

# re: HDU 3415 单调队列 2010-08-27 20:21 justmeh
另外,<queue>里面的queue定义中好像没有pop_front和pop_back成员函数吧!  回复  更多评论
  

# re: HDU 3415 单调队列 2010-09-12 12:29 baby_fly
@justmeh
用的是dequeue  回复  更多评论
  

# re: HDU 3415 单调队列 2011-07-02 21:42 asdf
nb  回复  更多评论
  

# re: HDU 3415 单调队列 2011-07-26 09:55 Chengsir
@baby_fly
学习了!  回复  更多评论
  

# re: HDU 3415 单调队列 2011-08-29 13:33 @fly
赞一个  回复  更多评论
  

# re: HDU 3415 单调队列 2013-07-15 13:26 KissLL
话说,sum数组为什么只开10W就能过,如果n=100000,k=100000,明显要开20W啊  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理