NC14583 消灭糖糖

消灭萌萌的糖糖

题目

https://ac.nowcoder.com/acm/problem/14583
来源：牛客网

从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1.现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。

思路

假如不发功，消灭糖糖的思路为从后往前遍历糖糖，维护两个类别中最大bi的两个糖糖，判断当前糖糖的bi值是否比最大糖糖的bi值小，如果小则被消灭，糖糖数量-1。
考虑法功，判断糖糖A是否能被其后面的糖糖B消灭，假设糖糖B之后发功了m次，A到B之间发功了n次，判断能够否消灭糖糖A的条件为： ,等同于 ,也就是对最终的bi值进行比较。

算法Java描述

import java.text.*;
import java.math.*;
public class Main{
    static class TT{
        int a,b;
        TT(int x,int y){this.a=x;this.b=y;}
    }
    public static void main(String[] args)throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(bf.readLine().trim());
        while(T-->0){
            String[] nm=bf.readLine().split(" ");
            int n=Integer.parseInt(nm[0]);
            int m=Integer.parseInt(nm[1]);
            TT[] tts=new TT[n];
            int[] dp=new int[n+1];
            for(int i=0;i<n;++i){
                String[] abStrs=bf.readLine().split(" ");
                int ai=Integer.parseInt(abStrs[0]);
                int bi=Integer.parseInt(abStrs[1]);
                tts[i]=new TT(ai,bi);
            }
            for(int i=1;i<=m;++i){dp[Integer.parseInt(bf.readLine())-1]++;}
            for(int i=n-1;i>=0;--i){
                dp[i]+=dp[i+1];
                tts[i].b+=dp[i];
            }
            int[] maxB={0,0};
            int res=n;
            for(int i=n-1;i>=0;--i){
                int curra=tts[i].a;
                int currb=tts[i].b;
                if(maxB[(~curra)&1]>currb){res--;}
                maxB[curra]=Math.max(maxB[curra],currb);
            }
            System.out.println(res);
        }
    }
}