糖糖别胡说，我真的不是签到题目题解

糖糖别胡说，我真的不是签到题目

https://ac.nowcoder.com/acm/problem/14583

知识点:后缀和

题目读了一会才明白过来什么意思，怪自己眼神不好看不清题意。

刚开始复杂度为T*n*m结果TLE了，于是加了一个temp数组改为T*n就过了。

首先我们应该明白一个事情，就是要判断第i个糖糖后面的糖糖是否能击杀他。

我们发现娇姐在第i秒发功前后对第i个糖糖所能击杀前面的糖糖没有影响，影响的是第i个糖糖是否能被后面的糖糖击杀。

所以我们可以直接先算出所有糖糖在娇姐发功后的b_i,这样的话我用一个temp数组记录每一个位置的糖糖所要增加的bi 的量。

然后我们需要用后缀和来维护第i个糖糖之后不同组别的最大值，需要用两个next数组来维护对应的组别.

来判断第i个糖糖的bi是否比next[i]小，如果小的话就会被击杀,sum--；

最后输出存活的糖糖个数就ok了，java代码如下。

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int T = (int)in.nval;
        for(int t=0;t<T;t++)
        {
        in.nextToken();
        int n = (int)in.nval;
        in.nextToken();
        int m = (int)in.nval;
        int a[] = new int[n+1];
        int b[] = new int[n+1];
        int c[] = new int[m];
        int next0[] = new int[n+1];
        int next1[] = new int[n+1];
        for(int i=1;i<=n;i++)
        {
            in.nextToken();
            a[i] = (int)in.nval;
            in.nextToken();
            b[i] = (int)in.nval;
        }
        
        int temp[] = new int[n+1];
        for(int i=0;i<m;i++)
        {
            in.nextToken();
            c[i] = (int)in.nval;
            temp[c[i]]++;
        }
        for(int i=n-1;i>=1;i--)
        {
            temp[i]+= temp[i+1];
        }
        for(int i=1;i<=n;i++)
            b[i] += temp[i];
            if(a[n]==0)
        {
            next0[n] = b[n];
            next1[n] = 0;
        }
        else{
            next1[n] = b[n];
            next0[n] = 0;
        }
            for(int i=n-1;i>=1;i--)
        {
             if(a[i]==0)
            {
                     next0[i] = Math.max(b[i],next0[i+1]);
                     next1[i] = next1[i+1];
            }
            else{
                    next1[i] = Math.max(b[i],next1[i+1]);
                    next0[i] = next0[i+1];
                }
        }
            int sum=n;
        for(int i=1;i<n;i++)
        {
                if(a[i]==0&&b[i]<next1[i])
                {
                    sum--;
                    
                }
            else if(a[i]==1&&b[i]<next0[i])
                {
                    sum--;
                }
        }
           out.println(sum);
        }
        out.flush();
    }
                  }