阿祁的部落格

Atcoder Beginner Contest 252 F - Bread 解題心得( 題目 )

解題概念:greedy

解題方法:本題利用pq，把問題倒過來看就可以解題了!

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

//Date:2022/05/22

import java.util.*;

import java.io.*;

public class Main {

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

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static long ret;

    public static int reti, rd;

    public static final int mod=998244353;

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

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

        final int n=readint();

        long l=readlong();

        long cnt=0,ans=0;

        long x;

        PriorityQueue<Long> pq=new PriorityQueue<Long>();

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

            x=readint();

            cnt+=x;

            pq.offer(x);

        }

        if(cnt<l) {

            pq.offer(l-cnt);

        }

        while(pq.size()!=1) {

            x=pq.poll()+pq.poll();

            ans+=x;

            pq.offer(x);

        }

        System.out.println(ans);

    }

    

 

    public static int readint() throws Exception{

        reti=0;

        while(rd<48||rd>57) {

            rd=br.read();

        }

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

            reti*=10;

            reti+=(rd&15);

            rd=br.read();

        }

        return reti;

    }

    public static long readlong() throws Exception{

        ret=0;

        while(rd<48||rd>57) {

            rd=br.read();

        }

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

            ret*=10;

            ret+=(rd&15);

            rd=br.read();

        }

        return ret;

    }

}