侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【贪心, 二分】线段和点

GabrielxD
2023-04-25 / 0 评论 / 0 点赞 / 116 阅读 / 809 字
温馨提示:
本文最后更新于 2023-04-25,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

试题 算法提高 线段和点


nn 个点和 mm 个区间,点和区间的端点全部是整数。

对于点 aa 和区间 [b,c][b,c] ,若 aba\ge baca \le c ,称点 aa 满足区间 [b,c][b,c]

求最小的点的子集,使得所有区间都被满足。

输入

第一行两个整数 n,mn, m

以下 nn 行 每行一个整数,代表点的坐标。

以下 mm 行 每行两个整数,代表区间的范围。

输出

输出一行,最少的满足所有区间的点数,如无解输出 1-1

样例输入

5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9

样例输出

2

数据规模和约定

  • 1n,m100001\le n,m \le 10000
  • 0点和区间的坐标500000 \le 点和区间的坐标 \le 50000

解题

方法一:贪心算法 二分查找

思路

贪心策略:

  1. 把所有区间按照右端点升序排序,把所有点升序排序;
  2. 维护 pp 为当前被选取的点的坐标,初始化为 1-1
  3. 枚举所有区间:
    • 如果当前区间左端点大于当前选取的点 pp ,则说明该区间已经无法被 pp 满足,需要选取一个新的点来满足该区间,二分查找最后一个小于等于当前区间右端点的点:
      • 如果该点不能满足当前区间( p[当前区间左端点,当前区间右端点]p \notin [当前区间左端点, 当前区间右端点] ),就表明点集中已经没有点可以满足当前区间,也就是无解,直接输出 1-1 ,退出程序。
      • 否则该点是可以满足当前区间的最优点,把 pp 置为该点并从点集中删除该点(注意不要改变序列的升序属性)。
    • 否则说明 pp 可以满足当前区间,什么也不做直接进入下一次迭代。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int[][] segs;
    static int[] pts;

    static int search(int x) {
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (pts[mid] <= x) l = mid;
            else r = mid - 1;
        }
        return r;
    }

    static void del(int idx) {
        for (int i = idx; i < n - 1; ++i) pts[i] = pts[i + 1];
        --n;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); n = (int) in.nval;
        in.nextToken(); m = (int) in.nval;
        pts = new int[n];
        segs = new int[m][2];
        for (int i = 0; i < n; ++i) {
            in.nextToken(); pts[i] = (int) in.nval;
        }
        for (int i = 0; i < m; ++i) {
            in.nextToken(); segs[i][0] = (int) in.nval;
            in.nextToken(); segs[i][1] = (int) in.nval;
        }
        Arrays.sort(segs, (a, b) -> a[1] - b[1]);
        Arrays.sort(pts);
        int p = -1, cnt = 0;
        for (int[] seg : segs) {
            int l = seg[0], r = seg[1];
            if (p < l) {
                int idx = search(r);
                p = pts[idx];
                if (p < l || p > r) {
                    System.out.println(-1);
                    return;
                }
                ++cnt;
                del(idx);
            }
        }
        System.out.println(cnt);
    }
}
0

评论区