阿祁的部落格

ZeroJudge g111-復仇之戰 解題心得( 題目 )

解題方法:這題在解題報告裡面有看到有人使用兩個前綴和，但其實不用，有省記憶體卻不增加執行時間的做法:

首先我們可以發現以下性質(用小畫家好難畫!!):

假設上面的五個圈圈代表五群，假設選擇不要第一個的距離總合為L (其實就是b+d)，則選第三群就是L+a-b，發現了嗎? 只要每次加前段距離減後段距離(像是選第五個是L+a-b+c-d)，紀錄最小的那次就是答案! 不過最後我們發現L是多少其實不影響結果，反正比較的時候都會消掉，所以其實我們可以直接不理會他。

註:雖然題目沒特別說明，不過一定是選奇數軍團才符合題意。

參考程式碼( 如果有更好意見可在下方留言，以做為本文章之補充，感謝! ):

//Author:En Chi Tsung(欉恩祁)

//Date:2021/10/23

import java.io.*;

public class zjg111 {

    public static void main(String[] args) throws Exception {
 
       BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 
       String[] ll=br.readLine().split(" ");
 
       final int l=Integer.parseInt(ll[0]);
 
       boolean b=true;//是否為奇數組
 
       int min=0;//目前最小距離
 
       int rt=1;//紀錄輸出結果
 
       int sum=0;//目前距離總和
 
       int d=0;//和上次的距離
 
       int i=0;//位置
 
       int num=1;
 
       for(;;i++) {
 
           if(br.read()=='p') {
 
               break;
 
           }
 
       }
 
       for(;i<l;i++) {
 
           if(br.read()=='p') {
 
               if(b) {
 
                   sum+=d;
 
               }
 
               else {
 
                   sum-=d;
 
                   num+=2;
 
                   if(sum<min) {
 
                       min=sum;
 
                       rt=num;
 
                   }
 
               }
 
               b=!b;//奇變偶，偶變奇
 
               d=0;
 
           }
 
           else {
 
               d++;//不是d則距離+1
 
           }
 
       }
 
       System.out.println(rt);
 
   }

}