1408D - Searchlights （思维、枚举）

电玩女神 2021-07-16 11:03 264阅读 0赞

[题目][Link 1]

从结果来分析，最小的步数必然是往右走多少步使一部分盗贼到达安全区域，然后再向上走一部分使余下的盗贼到达安全区域。那么我们从0到1e6+1枚举所有向右走的步数加上在该步数下最小向上走的步数，取其中最小值即为答案。那么问题来了，这个最小向上走的步数我们如何能够快速得到答案？其实只需要一个从后往前遍历记录的向上移动所需最大值数组即可。

简单来说就是，对于一个盗贼x,y，灯塔tx，ty，可以让盗贼向右移动tx-x+1使其脱离范围，也可以使其向上移动ty-y+1使其脱离范围。然后我们用一个数组dis\[tx-x+1\]=max(dis\[tx-x+1\],ty-y+1)记录在最小向右移动tx-x+1就能脱离的情况下，最小向上移动多少能够脱离。然后从0开始遍历向右移动的步数，假设遍历到10，即10以前的都可以通过向右移动离开范围，10以后的需要向上移动取10以后所有存在的情况的最大向上移动的值就可以让10以后的情况所有脱离。

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int tx[Max], ty[Max], x[Max], y[Max], dis[Max], ma[Max];
    
    int main()
    { 
    	int n, m;cin >> n >> m;
    	for (int i = 1;i <= n;i++) cin >> x[i] >> y[i];
    	for (int i = 1;i <= m;i++) cin >> tx[i] >> ty[i];
    	for (int i = 1;i <= n;i++)
    	{ 
    		for (int j = 1;j <= m;j++)
    		{ 
    			if (x[i] > tx[j] || y[i] > ty[j])continue;
    			dis[tx[j] - x[i] + 1] = max(dis[tx[j] - x[i] + 1], ty[j] - y[i] + 1);
    		}
    	}
    	for (int i = 1e6+2;i >= 0;i--) ma[i] = max(ma[i + 1], dis[i]);
    	int ans = 1e9;
    	for (int i = 0;i <= 1e6+2;i++)
    	{ 
    		ans = min(ans, i + ma[i + 1]);	
    	}
    	cout << ans << endl;
    }

[Link 1]: https://codeforc.es/problemset/problem/1408/D

发表评论取消回复

表情：

评论列表（有 0 条评论，264人围观）

还没有评论，来说两句吧...

相关阅读

相关如何枚举一个枚举

问题描述：如何在 C\ 中枚举 enum？例如，以下代码无法编译： public enum Suit { Spa

今天药忘吃喽~/ 2024年03月31日 17:45/ 0 赞/ 111 阅读

相关【枚举】CF1660 D

[Problem - 1660D - Codeforces][] 题意： ![208a35e52d4f4427a5e8eabf77f136e7.png][] 思路：思

缺乏、安全感/ 2024年03月23日 21:52/ 0 赞/ 55 阅读

相关【枚举，构造】CF1582 C D

[Problem - C - Codeforces][] 题意： ![41aba6a6704a46188f11720ce4b622e5.png][] ![35a7376c

旧城等待，/ 2024年03月23日 18:48/ 0 赞/ 74 阅读

相关【枚举+DS】CF1831D

不懂，m d，挂着再说 [Problem - D - Codeforces][] 题意： ![13d3e88892634f35907141b95608275c.png][

红太狼/ 2024年03月16日 10:41/ 0 赞/ 28 阅读

相关【*1500 枚举】CF1487D

又到了日常写水题环节.... 感觉这题只有\1300.... [Problem - D - Codeforces][] 题意：给定N 问你存在多少个三元组(a,b,

àì夳堔傛蜴生んèń/ 2024年03月16日 10:35/ 0 赞/ 53 阅读

相关【枚举】信息类枚举

> `前言` 比如用户信息里面有个等级，12345。通常，我们是建一个枚举类。替代方法：在实体类下添加自定义获取名称的方法。好处：如果项目服务很多，方

拼搏现实的明天。/ 2022年12月24日 01:54/ 0 赞/ 255 阅读

相关 d枚举转串

string enum_to_str(E)(E v) if (is(E == enum)) { final switch (v) with(E

淡淡的烟草味﹌/ 2022年08月28日 11:42/ 0 赞/ 208 阅读

相关枚举

JDK1.5之前需要自定义枚举类 JDK 1.5 新增的 enum 关键字用于定义枚举类若枚举只有一个成员, 则可以作为一种单例模式的实现方式枚举类对象的属性

亦凉/ 2022年03月22日 02:54/ 0 赞/ 314 阅读

相关枚举

枚举什么是枚举？枚举指的是在一定范围内取值，这个值必须是枚举类型中的任意一个，而且只能够取其中的一个枚举的特点： 1.枚举的本质就是一个Java类

叁歲伎倆/ 2022年03月18日 01:28/ 0 赞/ 368 阅读

相关 1408D - Searchlights （思维、枚举）

[题目][Link 1] 从结果来分析，最小的步数必然是往右走多少步使一部分盗贼到达安全区域，然后再向上走一部分使余下的盗贼到达安全区域。那么我们从0到1e6+1枚举所有

电玩女神/ 2021年07月16日 11:03/ 0 赞/ 265 阅读