阿祁的部落格

CSES 1189 - Food Division 解題心得( 題目 )

解題概念:三分搜尋法

解題方法:這題是個環狀的，所以很麻煩，但我們可以簡化題目變成一個直線的桌子，前提是先把第1人和最後1人之間的交換先計算，但我們顯然不知道要怎樣是最好的。

我們可以透過爆力法，但是顯然太慢，而二分搜尋在這也不管用，原因是沒有單調性，假設第1人給了最後1人x個食物(注意x可能為負)，總耗費為y，畫出來的函數是一個類似二次曲線、凹口向上的形狀，所以可以改使用三分搜尋法逼近。

Java參考程式碼(更好意見可留言於下方，謝謝!)

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

//Date:2021/02/04

import java.io.*;

public class cses1189 {

    public static int ret,r,n;

    public static long cnt;

    public static final long inf=(long)Math.pow(10,11)+5;

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));   

    public static long[] a=new long[200005];

    public static long[] b=new long[200005];

    public static long[] c=new long[200005];

    public static void main(String[] args) throws Exception{

        n=readint();

        for(int i=0;i<n;i++) {

            a[i]=readint();

        }

        for(int i=0;i<n;i++) {

            b[i]=readint();

        }

        System.out.println(TIS());

    }

    

    public static long TIS() {

        long L=-inf,R=inf;

        long ML,CL,MR,CR;

        while(R-L>2) {

            ML=L+(R-L)/3;

            MR=R-(R-L)/3;

            CL=cal(ML);

            CR=cal(MR);

            if(CL>=CR) {

                L=ML;

            }

            else {

                R=MR;

            }

        }

        return Math.min(cal(L),Math.min(cal(L+1),cal(R)));

    }

    

    public static long cal(long x) {

        copy();

        c[0]+=x;

        c[n-1]-=x;

        cnt=Math.abs(x);

        for(int i=0;i<n;i++) {

            cnt+=Math.abs(c[i]-b[i]);

            c[i+1]+=(c[i]-b[i]);

        }

        return cnt;

    }

    

    public static void copy() {

        for(int i=0;i<n;i++) {

            c[i]=a[i];

        }

    }

    

    public static int readint() throws Exception {

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;

    }

}