糖糖别胡说，我真的不是签到题目 题解
糖糖别胡说，我真的不是签到题目
https://ac.nowcoder.com/acm/problem/14583
知识点:后缀和
题目读了一会才明白过来什么意思，怪自己眼神不好看不清题意。
刚开始复杂度为T*n*m结果TLE了，于是加了一个temp数组改为T*n就过了。
首先我们应该明白一个事情，就是要判断第i个糖糖后面的糖糖是否能击杀他。
我们发现娇姐在第i秒发功前后对第i个糖糖所能击杀前面的糖糖没有影响，影响的是第i个糖糖是否能被后面的糖糖击杀。
所以我们可以直接先算出所有糖糖在娇姐发功后的bi,这样的话我用一个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();
}
} 
查看5道真题和解析
