洛谷 P2782 友好城市 线性DP 最长上升子序列 二分查找 lower_bound

这篇具有很好参考价值的文章主要介绍了洛谷 P2782 友好城市 线性DP 最长上升子序列 二分查找 lower_bound。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍑 算法题解专栏


🍑 洛谷:友好城市

题目描述

有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避免事故。编程帮助政府做出一些批准和拒绝申请的决定,使得在保证任意两条航道不相交的情况下,被批准的申请尽量多。

输入格式

第1行,一个整数N,表示城市数。

第2行到第n+1行,每行两个整数,中间用一个空格隔开,分别表示南岸和北岸的一对友好城市的坐标。

输出格式

仅一行,输出一个整数,表示政府所能批准的最多申请数。

样例 #1

样例输入 #1

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

样例输出 #1

4

提示

50% 1<=N<=5000,0<=xi<=10000

100% 1<=N<=2e5,0<=xi<=1e6


🍑 题意

🍤 每个城市只能建立一座桥
🍤 桥不能交叉

🍑 Arrays.BinarySearch(数组,起点,终点(不包含),待查找的值)
👨‍🏫 参考文档

洛谷 P2782 友好城市 线性DP 最长上升子序列 二分查找 lower_bound
🍑 insert point(插入点)

🍤 初始化
数组 a {1,3,5,7}
查找值:4 
🍤 实测出真知
BinarySort(a,4) == -3
设 insert point 为 x
则 -x - 1 = -3  --> x = -(-3 + 1) = 3
👨‍🏫 为什么插入点是 3 呢
假设:4 已经插入到数组了,则 a = {1,3,4,5,7}
可见:第一个大于 4 的元素5 的下标为 3

🍑 输入数据量过多,使用快读
🍑 扩展:C++ STL 中的 lower_bound 参考

有序的情况下,lower_bound返回指向第一个值不小于val的位置
也就是返回第一个大于等于val值的位置。(通过二分查找)文章来源地址https://www.toymoban.com/news/detail-434409.html

🍑 AC代码

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

public class Main
{
	static int N = 200010;
	static Pair[] a = new Pair[N];
	static int[] f = new int[N]; // f[i]=长度为i的IS最小最后一个数

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

//	友好城市类
	static class Pair
	{
		int l, r;

		Pair(int l, int r)
		{
			this.l = l;
			this.r = r;
		}
	}

//	在数组中找到 >= x 的所有数中的最小值(下标) // 手动实现 lowerBound
	static int binarySearch(int[] a, int l, int r, int x)
	{
		while (l < r)
		{
			int m = l + r >> 1;
			if (a[m] < x)
				l = m + 1;
			else
			{
				r = m;
			}
		}
		return l;
//		if (l == r)
//			return l;
//		int m = l + r + 1 >> 1;
//		if (x > a[m])// m 符合条件,结果在右区间
//			return binarySearch(a, m, r, x);
//		else// m 不符合条件,结果在左区间
//		{
//			return binarySearch(a, l, m - 1, x);
//		}
	}

	public static void main(String[] args) throws IOException
	{
//		Scanner sc = new Scanner(System.in);
//		int n = sc.nextInt();
		int n = Integer.parseInt(in.readLine());
		int p = 0;
		for (int i = 0; i < n; i++)
		{
			String[] ss = in.readLine().split(" ");
			int l = Integer.parseInt(ss[0]);
			int r = Integer.parseInt(ss[1]);

//			int l = sc.nextInt();
//			int r = sc.nextInt();
			a[i] = new Pair(l, r);
		}

		Arrays.sort(a, 0, n, (o1, o2) -> o1.l - o2.l);

		for (int i = 0; i < n; i++)
		{
			if (a[i].r > f[p])
			{
				p++;
				f[p] = a[i].r;
			} else
			{
//				int pos = Arrays.binarySearch(f, 1, p + 1, a[i].r);// AC
				int pos = binarySearch(f, 1, p, a[i].r); //手动实现
				if (pos < 0)// 加一层保险
					pos = -(pos + 1);// 本题保证了城市不会重复,所以可以直接按返回 -(插入点-1) 处理
				f[pos] = a[i].r;
			}
		}
		System.out.println(p);
	}
}

🍑 暴力线性DP O(n^2) (50%)

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
	static int N = (int) 2e5 + 10;
	static Pair[] w = new Pair[N];
	static int[] f = new int[N];

	static class Pair
	{
		int x;
		int y;

		public Pair(int x, int y)
		{
			super();
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++)
		{
			int x = sc.nextInt();
			int y = sc.nextInt();
			w[i] = new Pair(x, y);
		}
		Arrays.sort(w, 0, n, (o1, o2) -> o1.y - o2.y);

//		DP
		int res = 0;
		for (int i = 0; i < n; i++)
		{
			f[i] = 1;
			for (int j = 0; j < i; j++)
				if (w[j].x < w[i].x)
					f[i] = Math.max(f[i], f[j] + 1);
			res = Math.max(res, f[i]);
		}

		System.out.println(res);
	}
}

到了这里,关于洛谷 P2782 友好城市 线性DP 最长上升子序列 二分查找 lower_bound的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【重点】【DP】300. 最长递增子序列

    题目 更好的方法是耐心排序,参见《算法小抄》的内容!!! 基础解法必须掌握!!!

    2024年01月17日
    浏览(46)
  • 【洛谷】P2690 [USACO04NOV] Apple Catching G(dp or 记忆化搜索)

    ACcode: 记忆化搜索: over~

    2024年02月15日
    浏览(30)
  • C++---树形DP---树的最长路径(每日一道算法2023.5.4)

    注意事项: 本题为\\\"树与图的DFS深度优先遍历—树的重心\\\"的近似题,同时涉及到 单链表模拟邻接表存储图 的操作,建议先理解那篇文章。 题目: 给定一棵树,树中包含 n 个结点(编号1~n)和 n−1 条无向边,每条边都有一个权值。 现在请你找到树中的一条最长路径。 换句话

    2024年02月02日
    浏览(36)
  • 动态规划入门第4课,经典DP问题3 ----公共最长子序列

      练习 第1题     最长公共子串 查看测评数据信息 给出2个小写字母组成的字符串,求它们最长的公共子串的长度是多少? 例如:”abcdefg” 与”xydoeagab”。有最长的公共子串”deg”, 答案为:3。 输入格式   第一行:一个字符串,长度不超过1000。 第二行:一个字符串,

    2024年02月15日
    浏览(38)
  • 【LeetCode】1143.最长公共子序列(闫氏dp可视化无分析)

      推荐一下这道题的可视化过程 最长公共子序列 - 动态规划 Lngest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili  

    2024年02月15日
    浏览(43)
  • 【动态规划】NK刷题记之DP8乘积为正数的最长连续子数组

    ❤️博客主页: 小镇敲码人 🍏 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌞在一切变好之前,我们总要经历一些不开心的日子,这段日子也许很长,也许只是一觉醒来。有时候,选择快乐,更需要勇气。 🍉 如果你也迷失在了路上,对人生充满了迷惘,不要害怕,冷静下来,

    2024年02月09日
    浏览(43)
  • 动态规划(DP)入门——线性DP

    在了解线性DP之前,我们首先要知道什么是动态规划,即为将一种复杂问题,分解成很多重叠的子问题,并通过子问题的解得到整个问题的解的算法。听起来比较抽象,动态规划简单来说就是确定问题的状态,通常题目都会提示,一般为“到第i个为止,xx为j(xx为k)的方案数/最

    2024年02月19日
    浏览(47)
  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 题目1 :数字三角形。 解题思路:直接DP即可, f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ,注意 f[i-1][j] 不存在的情况(最后一个点)和 f[i-1][j-1] 不存在的情况(第一个点)。

    2024年02月04日
    浏览(49)
  • 算法专题:线性DP

    参考练习习题总集 第一道题就是困难题让我很难蚌,真是磨人啊。 嗨嗨嗨,思想差不多的,又水一道困难题。 记忆化搜索。这里的记忆化搜索本质就是线性DP。做这道题时真是气死我了,一开始明明记着长度为0的时候需要特判,但是后面做着做着就忘了加上去,交了一次又

    2024年02月19日
    浏览(36)
  • 动态规划——线性DP

    暴力搜索:由可行的所有起点出发,搜索出所有的路径。 但是深搜的算法时间复杂度要达到 O ( 2 n ) O(2^n) O ( 2 n ) (每个数都有选或不选的两个选择),指数级的时间复杂度在本题中( n ≤ 100 n≤100 n ≤ 100 )显然是不能接受的。那么再观察这个这棵递归树,可以发现其中有很

    2024年01月19日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包