洛谷 P4754 True Vegetable 题解【贪心】【差分】【二分答案】

作者: wjyyy 分类: 二分,差分,解题报告,贪心 发布时间: 2018-07-15 10:45

点击量:19

 

   题面全是坑的题= =

 

题目描述

小A现在有N道题,编号为1,2,⋯,N。每道题的起始毒瘤程度为0或1。在每天,小A可以将编号连续的K道题的毒瘤程度+1。但小B因为本身比较菜,不是很愿意小A出毒瘤题,所以在\(w_i\)天开始时可以向第\(x_i\)题传播\(v_i\)​点的菜气,使得第\(x_i\)的毒瘤程度减少\(v_i\)​点(减后可以为负)。这里我们假定菜是有限的,在释放了\(v_i\)点的菜气后,小B需要至少\(r_{v_i}\)个回合不能释放菜气。现在小A知道了小B释放菜气的计划,他想知道他至少需要多少个回合可以使得每道题的毒瘤程度至少为1。

输入输出格式

输入格式:

第一行输入四个整数,N,M,K,L,分别为题目的数量,小B的操作数量,每次连续增加毒瘤程度题目的数量和释放菜气的最大值。

 

第二行输入N个整数\(a_1,a_2,\cdots,a_N\),分别为N个题目的毒瘤程度。

 

第三行输入L个整数\(r_1,r_2,\cdots,r_L\),分别为释放1到L点菜气的冷却回合数。

 

接下来有M行,每行输入三个整数\(w_i,x_i,v_i\),表示小B在第\(w_i\)次回合开始时向第\(x_i\)题释放了\(v_i\)点的菜气。保证\( \{w_i\}\)为递增序列。

 

输出格式:

请输出小A将每道题的毒瘤程度加到至少为1最少需要的回合数。

 

输入输出样例

输入样例#1:
6 1 3 2
0 0 0 0 0 0
1 2
2 1 1
输出样例#1:
3
输入样例#2:
6 1 3 2
1 0 0 0 0 0
1 2
2 1 1
输出样例#2:
2
输入样例#3:
6 1 6 2
0 0 0 0 0 0
1 2
2 1 1
输出样例#3:
1

说明

\(1≤N,M≤5×10^5\)

\(1 \le K \le N\)

\(1 \le L \le 100\)

\(a[i] \in \{0,1\}\)

\(1 = r_1 < r_2 < \cdots < r_L \le 2 \times L\)

\(1 \le w_i \le N+L\)

\(w_i+r_{v_i} \le w_{i+1}\)

\(1 \le x_i \le N\)

\(1 \le v_i \le L\)

 

题解:

   首先,如果冷却时间内,B的技能受到影响,那么就转化为DP了。不过这个题有特殊条件:\(w_i+r_{v_i} \le w_{i+1}\),也就是说,这个题的冷却时间对决策没有影响。而继续看,还有一句话:\(1 = r_1 < r_2 < \cdots < r_L \le 2 \times L\)。也就是说,冷却时间一定是不短于造成的伤害数的,即\(\forall i\in [1,L] ,r_i\ge i\)。

 

   这样问题就具有了单调性。如果在一个时间点所有题的毒瘤程度已经全部加到1了,那在后面的时间点中一定不会再减少到1以下(即使有也可以在两次间隔时间内补回来)。这样一来就可以二分答案了,二分释放前i个技能,把a[i]从左到右扫一遍,一旦发现小于1,就把接下来k个全部加上1-a[i]。因为发现了一个数的a[i]小于1,它早晚都是要被加上的,从它开始向右延展k个一定最优,这就是贪心。不过当k很大的时候复杂度就会变成\(O(NK\log N)\),而我们的操作是从左往右的,所以可以用差分来控制。

 

   用一个数记录下现在的差分数是多少,并给i+k的地方打上差分减小标记。每次扫描到一个位置先把差分数减去差分减少标记,再加上a[i],就是现在的a[i]了。

 

数组越界搞得我一直98分。。。

 

Code:

#include<cstdio>
#include<cstring>
int w[510000],v[510000],x[510000];
int a[510000],b[510000];
int n,m,k;
int check(int X)
{
    memset(b,0,sizeof(b));
    for(int i=1;i<=X;i++)
        a[x[i]]-=v[i];
    int tt=0,d=0,p=0;
    for(int i=1;i<=n;i++)
    {
        d+=b[i];
        p=a[i]+d;
        if(p<1)
        {
            tt+=1-p;
            if(tt>=w[X+1])//超出直接返回不合法
            {
                tt=-1;
                break;
            }
            d+=1-p;
            if(i+k<=n)
                b[i+k]-=1-p;
        }
    }
    for(int i=1;i<=X;i++)
        a[x[i]]+=v[i];
    return tt;
}
int main()
{
    int l,r;
    scanf("%d%d%d%d",&n,&m,&k,&l);
    w[m+1]=0x3fffffff;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=l;i++)
        scanf("%d",&r);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&w[i],&x[i],&v[i]);
    r=m;
    l=0;
    int mid;
    while(l<r)//二分释放技能数
    {
        mid=l+r>>1;
        if(check(mid)==-1)
            l=mid+1;
        else
            r=mid;
    }
    printf("%d",check(l));
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */