题解 P2629 【好消息,坏消息】

2018-09-26 18:30:55


z

你没有发现两个字里的blog都不一样嘛 qwq

题目描述-->p2629 好消息,坏消息

历程

刚开始看到这个题,发现是需要维护区间和,满心欢喜敲了一通线段树,简单debug之后交上去 $45pts$ ?

改代码的时候开始考虑这样做的正确性.

维护区间和,前后两个的区间和加起来一定等于整个区间的区间和,那我和直接求和有什么区别?

再次读题

发现必须要求每一个时刻老板的怒气值都 $\geq 0$ 才行.

xjb分析

既然维护区间和行不通,考虑改变线段树所维护的东西.

考虑维护些什么?

我们需要维护一个区间的最小值,才能判断是否满足 $\geq 0$

而某一个位置的值,受前面位置的值的影响.

因此我们想到了前缀和.

即我们可以维护前缀和的最小值.

解决85%

既然想到了维护前缀和,那这样就很简单了.

根据题目所叙述的,我们需要从 $k,k_1,k_2 \dots n,1,2 \dots k-1$ 累加

所以我们要先判断后缀的最小值是否 $\leq 0$

显然,我们的前缀和的计算为 $sum_i=\sum_{j=1}^{i}a_i$

后缀部分 $\sum_{i=k}^{n}a_i$ 的计算要减去 $sum_{k-1}$

又因为题目要求的计算顺序,我们需要考虑后缀和与前缀最小值的和是否 $\geq 0$

所以很容易写出这部分的代码

    for(R int i=2;i<=n;i++)
    {
        if(query(1,1,n,i,n)-sum[i-1]<0)continue;
        if(sum[n]-sum[i-1]+query(1,1,n,1,i-1)>=0)
            ans++;
    }   

看到上面的 $85$ %了没?

如果只单纯判断这些情况的话只能get到 $85pts$

考虑被遗忘的情况

检查一番,我们发现题目中这一句话

uim必须按照时间的发生顺序逐条将消息告知给老板

突然醒悟

我们还可以从 $1$ 到 $n$ 告诉老板!

再加上判断是否整个区间的前缀最小值 $\leq 0$ 即可.

综上,我们的问题就得以解决了!

---------------------代码---------------------

#include<bits/stdc++.h>
#define R register
#define N 1000008
#define ls o<<1
#define rs o<<1|1
using namespace std;
int tr[N<<2],ans,n,sum[N];
inline void up(int o){tr[o]=min(tr[ls],tr[rs]);return;};
void build(int o,int l,int r)
{
    if(l==r)
    {
        tr[o]=sum[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    up(o);
}
int query(int o,int l,int r,int x,int y)
{
    if(x<=l and y>=r)return tr[o];
    int mid=(l+r)>>1,res=2147483647;
    if(x<=mid)res=min(res,query(ls,l,mid,x,y));
    if(y>mid)res=min(res,query(rs,mid+1,r,x,y));
    return res;
}
int main()
{
    scanf("%d",&n);
    for(R int i=1,x;i<=n;i++)scanf("%d",&x),sum[i]=sum[i-1]+x;
    build(1,1,n);
    for(R int i=2;i<=n;i++)
    {
        if(query(1,1,n,i,n)-sum[i-1]<0)continue;
        if(sum[n]-sum[i-1]+query(1,1,n,1,i-1)>=0)
            ans++;
    }   
    printf("%d",ans+(tr[1]>=0));
}