1672 区间交

1 秒 131,072 KB 40 分 4 级题

思路：

先按照区间左端点排序

然后维护一个优先队列，存放右端点

循环m个区间

队列共三种操作

• 把每个区间的右端点加入
• 如果区间左端点>队列的值，弹出
• size>k时，弹出至k个

• 队列每次size为k时，计算区间的和，队列第一个-（当前左端点-1）取最大值

  代码：

package _51_node.greedy;import java.util.Arrays;import java.util.PriorityQueue;import java.util.Scanner;public class ex_1672 {    /**     * 1672 区间交     * 1 秒  131,072 KB 40 分 4 级题     * @param args     */    public static void main(String[] args) {        Scanner cin = new Scanner(System.in);        int n, k, m, x;        n = cin.nextInt();        k = cin.nextInt();        m = cin.nextInt();        long[] sum = new long[n+1];        PriorityQueue
    
      q = new PriorityQueue<>();        Pair[] pair = new Pair[m];        for (int i = 1; i <= n; i++) {            x = cin.nextInt();            sum[i] = sum[i - 1] + x;        }        for (int i = 0; i < m; i++) {            pair[i] = new Pair(cin.nextInt(), cin.nextInt());        }        Arrays.sort(pair);        long ans = 0;        for (int i = 0; i < m; i++) {            q.add(pair[i].r);            while (!q.isEmpty()) { //剔除没有相交区域的                if (q.peek() < pair[i].l) q.poll();                else break;            }            while (q.size() > k) q.poll();//去除小区间            if (q.size() == k) ans = Math.max(ans, sum[q.peek()] - sum[pair[i].l-1]);        }        System.out.println(ans);    }    static class Pair implements Comparable
     
       {        int l;        int r;        public Pair(int l, int r) {            this.l = l;            this.r = r;        }        @Override        public int compareTo(Pair o) {            if (l > o.l) return 1;            return -1;        }    }}