阿祁的部落格

ZeroJudge g597 - 生產線 解題心得( 題目 )

心得:這次APCS的題目似乎較難，需要以更靈活的運用所學。

先提別人的作法(比較不好的):

1.每次工作把範圍內的機器都加上這份工作的資料量，最後排序資料量小的配花費時間多的:

這樣會TLE，只能拿30%，因為修改總時間最糟糕為O(m^2)!

2.線段樹或BIT:

這是我本來想到的，可是其實這些資料結構都不好實作，而且其實有更簡單的方法，另外這些複雜度反而比較高。

解題概念:差分、前綴和

解題方法:我們定義d[i]=a[i]-a[i-1](假設機器為1~n，設a[0]=0)，而a[i]是我們最後想得到的結果，我們維護陣列d，那a怎麼求呢?當我們求a[5]，其實就是d[1]+d[2]+...+d[5](d的前綴和)，會發現互相會消掉，而這種資料結構的好處在於說，如果我更動一個範圍的值，對於d[i]只有範圍最前面跟最後面的要更動(其他效果會抵消)，這樣修改的複雜度可降為O(m)。

最後只要把a、t(耗時)排序，小的配大的就是答案!

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

import java.io.*;

import java.util.*;

public class zjg597 {

    public static int ret,r;

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

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

        final int n=readint();

        final int m=readint();

        long[] d=new long[n+5];//差分陣列

        long[] arr=new long[n];//總資料量

        long[] t=new long[n];//時間

        int a,b,c;

        long csum=0,rs=0;

        Arrays.fill(d,0);

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

            a=readint();//輸入

            b=readint();

            c=readint();

            d[a-1]+=c;

            d[b]-=c;

        }

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

            csum+=d[i];

            arr[i]=csum;//求出資料量

        }

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

            t[i]=readint();//輸入


        }

        Arrays.sort(arr);

        Arrays.sort(t);

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

            rs+=arr[i]*t[n-i-1];//小配大

        }

        System.out.println(rs);

    }



    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;

    }

}