欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2021-03-22

程序员文章站 2024-03-19 10:03:40
...
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;

public class Solution {

    private static final int MaxM = 200000;
    private static final long[] f = new long[MaxM + 3];
    //Map<K,V> k 为工作开始时间,V是集合--> 已K为开始时间的工作 的结束时间 集合
    private static final HashMap<Integer, ArrayList<Integer>> all = new HashMap<>();
    private static final int[][] fee = new int[2][103];
    private static StreamTokenizer in;
    private static int N, M, K, last;

    private static PriorityQueue<Integer> pq = new PriorityQueue<>();

    private static void init() {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        init();
        int T = nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = nextInt();
            M = nextInt();
            for (int i = 0; i < M; i++) {
                int s = nextInt();
                int e = nextInt();
                ArrayList<Integer> aList = all.getOrDefault(s, new ArrayList<>());
                aList.add(e);
                all.put(s, aList);
                last = Math.max(last, e);//所有工作的 最后结束时间
            }
            for (int i = 1; i <= K; i++) {
                fee[0][i] = nextInt();
                fee[1][i] = nextInt();
            }
            dp();
            long ans = 0;
            for (int i = 1; i <= last; i++) {
                if (all.containsKey(i)) {
                    pq.addAll(all.get(i));
                    while (!pq.isEmpty() && pq.peek() < i) pq.poll();//将结束的工作 清出PQ
                    if (pq.size() > N) ans += f[pq.size() - N];//当工作数大于N时,从f[i]取 最低费用
                }
            }
            System.out.println("#" + tc + " " + ans);
            for (ArrayList<Integer> val : all.values()) val.clear();
        }
    }
    //完全背包 动态规划
    private static void dp() {
        Arrays.fill(f, Long.MAX_VALUE >> 1);
        f[0] = 0;
        for (int i = 1; i <= K; i++) {
            for (int j = fee[0][i]; j <= M; j++) {
                f[j] = Math.min(f[j], f[j - fee[0][i]] + fee[1][i]);
            }
        }
    }
}

相关标签: 不公开

推荐阅读