报告错误
如果你发现该网页中存在错误/显示异常,可以从以下两种方式向我们报告错误,我们会尽快修复:
- 使用 CS Club 网站错误 为主题,附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
Problem 2. Hoof, Paper, Scissors
题目大意
“石头 剪刀 布”-Bessie可以在FJ做出动作之前预测每个动作。但是她倾向于连续多次玩相同的手势。在整个游戏中她最多会切换一次手势。求Bessie可以赢得的最大游戏数。
思路
(1≤N≤100,000)如果直接模拟,复杂度是O(n^2),所以我们可以用前缀和数组,尝试每一个可能的组合PS SP HP PH SH HS。在前x步出一个,再在后N-x步换一个出。
复杂度
O(n)
import java.util.*;
import java.io.*;
public class hoofPaperScissors{
public static int findMax(int[] a,int[] b){
int max=0;
for(int i=0;i<a.length;i++){
max=Math.max(max,a[i]+b[b.length-1]-b[i]);
}
return max;
}
public static void main (String [] args) throws IOException{
BufferedReader br = new BufferedReader(new FileReader("hps.in"));
PrintWriter pr = new PrintWriter(new FileWriter("hps.out"));
int N=Integer.parseInt(br.readLine());
int[] P=new int[N];
int[] S=new int[N];
int[] H=new int[N];
int pi=0;
int si=0;
int hi=0;
for(int l=0;l<N;l++){
String word=br.readLine();
if(word.equals("P")) pi++;
P[l]=pi;
if(word.equals("H")) hi++;
H[l]=hi;
if(word.equals("S")) si++;
S[l]=si;
}
//System.out.println(Arrays.toString(P));
//System.out.println(Arrays.toString(H));
//System.out.println(Arrays.toString(S));
int[] maximum={findMax(P,S),findMax(S,P),findMax(H,P),findMax(P,H),findMax(S,H),findMax(H,S)};
//PS SP HP PH SH HS
Arrays.sort(maximum);
//System.out.println();
/*
System.out.println(findMax(P,S));
System.out.println(findMax(S,P));
System.out.println(findMax(H,P));
System.out.println(findMax(P,H));
System.out.println(findMax(S,H));
System.out.println(findMax(H,S));
*/
pr.println(maximum[5]);
pr.close();
}
}