竞赛讨论区 > E题求解:这样贪心错在哪了?
头像
tx163
发布于 04-06 14:24
+ 关注

E题求解:这样贪心错在哪了?

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeSet;
import java.util.concurrent.ForkJoinTask;

public class Main {
    static BufferedReader cin=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter cout=new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer st=new StreamTokenizer(cin);
    static Scanner sc=new Scanner(cin);
    static int MAXN=100005;
    static int n,m;
    static long a[]=new long[MAXN];
    static long b[]=new long[MAXN];
    public static void main(String[] args)throws IOException {
    	n=nextInt();
    	int q=nextInt();
    	for(int i=1;i<=n;i++) a[i]=nextLong();
    	for(int i=1;i<=n;i++) b[i]=nextLong();
    	while(q-->0){
    		int k=nextInt();
    		long res=0,base=0;
    		PriorityQueue<Long> pq=new PriorityQueue<>((a,b)->(b>=a?1:-1));
    		for(int i=1;i<=k;i++) {
    			pq.add(b[i]);
    			res+=a[i];
    			res+=b[i];
    		}
    		for(int i=k+1;i<=n;i++) {
    			base+=a[i];
    			if(base>=pq.peek()) break;
    			if(base+b[i]<=pq.peek()) {
    				res+=base+b[i]-pq.poll();
    				pq.add(b[i]);
    				base=0;
    			}
    		}
    		cout.println(res);
    	}
    	end();
    }
    public static void end() throws IOException {
        cout.flush();
        cout.close();
        cin.close();
    }
    public static double nextDouble()throws IOException{
        st.nextToken();
        return st.nval;
    }
    public static int nextInt() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    public static long nextLong()throws IOException{
        st.nextToken();
        return (long) st.nval;
    }
    public static String next()throws IOException{
        st.nextToken();
        return st.sval;
    }
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐