codeforces 338 E. Optimize! (线段树维护最小前缀和)

题目链接

题意:题意是由伪代码给出的。。手算模拟了一下(noip初赛即视感),题意大概是说,给出两个数组a和b,a数组长度为n,b数组长度为len,然后从a中截取连续的len个元素,称为数组s,如果存在一种方法使得s中元素和b中的元素一一对应且每组和都大于等于h,则称这个s是合法的。现在问a中有多少个合法的s。
具体来说,对于样例
5 2 10
5 3
1 8 5 5 7

s={8,5}和s={5,7}是有解的。
因为对于前者8+3>=10并且5+5>=10,对于后者5+5>=10,7+3>=10,因此答案为2
思路:

最重要的一部是,我们先将b排序,然后维护一个函数f[i],在排序后的b中找到一个最小的j,满足a[i]+b[j]>=h,然后让f[i]=j?

f[i]直接二分就可以得到。。

因为f[i]的值是使得a[i]满足条件的最小的b值。

然后我们观察发现。

f[i]大于等于len的元素个数最多有1个,不然无解。

f[i]大于等于len-1的元素个数最多有2个,不然无解。

f[i]大于等于i的元素个数最多由len+1-i个,不然无解。

设g[i]=len+1-i-sum[i],sum[i]=y[i]+y[i+1]+…+y[len]。

如果某个s中,对于所有的i,都有g[i]>=0,那么这个s就是合法的。

实际上我们没有必要去查询每个g[i],只要g[i]中最小的大于等于0,那么这个s就是合法的。

现在的问题就变成了动态维护一段长度为len的最小后缀和。

我的思路是整体覆盖,

当a数组的区间从[l,r]到[l+1,r+1]的时候,增加了a[r+1],假设f[r+1]=p,那么用线段树更新区间[1,p],都增加1.
减少了a[l],假设f[l]=q,那么同样用线段树维护,使得区间[1,q]都减少1.

讲道理应该也可以做吧。。。

不过被羊神@sheep教育说其实单点更新就可以。。。

1862480807

于是去学了下动态维护区间最大子段和的线段树做法:
bzoj 1756解题报告hit oj 2687 解题报告

 

然后单点更新维护最大后缀和就很容易了。

类似的做法,我们也维护一个最小前缀和。初始化的时候把1..len赋值成-1.

然后每次移动区间,从【l,r】移动到[l+1,r+1]的时候,将f[r+1]添加1,将f[l]减少1.

这样如果某个s中的任意前缀和都是等于0的,那么这个s就是合法的。

因此我们只需要维护最小前缀和。

代码是维护的最小前缀和

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz