题目
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
【问题描述】
小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。
更准确的说，小明定义 Alice 和 Bob“同时出现”的意思是：
在小说文本 中 Alice 和 Bob 之间不超过 K 个字符。
例如以下文本：
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，
分别是”Alice and Bob” 和”Bob. Alice”。
前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。
注意:
1.Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。
2.Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能 有字母。
例如 Bobbi 並不算出现了 Bob。
【输入格式】
第一行包含一个整数 K。 第二行包含一行字符串，只包含大小写字母、标点符号和空格。
长度不超 过 1000000。
【输出格式】
输出一个整数，表示 Alice 和 Bob 同时出现的次数。
【样例输入】
20
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
【样例输出】
2
【评测用例规模与约定】
对于所有评测用例，1≤ K ≤1000000。
答案
package competition3;
import java.util.Scanner;
public class RelevanceOfMy2
{
public static long result=0;
public static int K;
public static String text;
public static int length;
public static void main(String[] args)
{
Scanner in =new Scanner(System.in);
K=in.nextInt();
in.nextLine();
text=in.nextLine();
length=text.length();
int[] number1=new int[1000000];
int[] number2=new int[1000000];
int count1=0,count2=0;
in.close();
for(int x=0;x<length;x++)
{
if(!IsLetter(x-1) && x+4<length && !IsLetter(x+5) && text.substring(x, x+5).equals("Alice") )
{
number1[count1++]=x;
}
if(!IsLetter(x-1) && x+2<length && !IsLetter(x+3) && text.substring(x, x+3).equals("Bob") )
{
number2[count2++]=x;
}
}
if(count1==0 || count2==0)
{
result=0;
}
else
{
int left=0,right=-1;
for(int x=0;x<count1;x++)
{
while(right+1<count2 && number2[right+1]<=number1[x]+K+5)
{
right++;
}
while(number2[left]+3+K<number1[x])
{
left++;
}
result += right-left+1;
}
}
System.out.println(result);
}
public static boolean IsLetter(int index)
{
if(index<0 || index >=length)
return false;
char charAt = text.charAt(index);
return (charAt>='a' && charAt<='z')||(charAt>='A' && charAt<='Z');
}
}
package competition3;
import java.util.Scanner;
public class RelevanceOfMy3
{
public static long result=0;
public static int K;
public static String text;
public static int length;
public static int[] number1=new int[1000000];
public static int[] number2=new int[1000000];
public static int count1=0,count2=0;
public static void main(String[] args)
{
Scanner in =new Scanner(System.in);
K=in.nextInt();
in.nextLine();
text=in.nextLine();
length=text.length();
in.close();
for(int x=0;x<length;x++)
{
if(!IsLetter(x-1) && x+4<length && !IsLetter(x+5) && text.substring(x, x+5).equals("Alice") )
{
number1[count1++]=x;
}
if(!IsLetter(x-1) && x+2<length && !IsLetter(x+3) && text.substring(x, x+3).equals("Bob") )
{
number2[count2++]=x;
}
}
if(count1==0 || count2==0)
{
result=0;
}
else
{
for(int x=0;x<count1;x++)
{
int left = FindLeft(number1[x]-K-3);
if(number2[left]>number1[x]+K+5)
{
continue;
}
int right=FindRight(number1[x]+K+5);
result +=right-left+1;
}
}
System.out.println(result);
}
public static int FindLeft(int index)
{
int left=0,right=count2-1;
int middle;
while(left<right)
{
middle=left+right>>1;
if(index<=number2[middle])
{
right=middle;
}
else
{
left=middle+1;
}
}
return left;
}
public static int FindRight(int index)
{
int left=0,right=count2-1;
int middle;
while(left<right)
{
middle=left+right +1>>1;
if(index>=number2[middle])
{
left=middle;
}
else
{
right=middle-1;
}
}
return right;
}
public static boolean IsLetter(int index)
{
if(index<0 || index >=length)
return false;
char charAt = text.charAt(index);
return (charAt>='a' && charAt<='z')||(charAt>='A' && charAt<='Z');
}
}
对应的二分查找比它小的最大值和比它大的最小值
package competition3;
public class BinarySearch
{
public static int[] arr={1,3,5,8,9,12,14,18,19};
public static void main(String[] args)
{
System.out.println(BinarySearchSmall(0));
System.out.println(BinarySearchBig(15));
}
public static int BinarySearchSmall(int number)
{
int x=0,y=arr.length-1;
while(x<y)
{
int middle=x+y>>1;
if(number <= arr[middle])
{
y=middle;
}
else
{
x=middle+1;
}
}
return x;
}
public static int BinarySearchBig(int number)
{
int x=0,y=arr.length-1;
while(x<y)
{
int middle=x+y+1>>1;
if(number >= arr[middle])
{
x=middle;
}
else
{
y=middle-1;
}
}
return x;
}
}
Processed:
0.012, SQL:
8
