ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[洛谷P2678][NOIP2015 提高组] 跳石头(二分 + 贪心)

2022年3月29日 574点热度 0人点赞 0条评论

题目链接:P2678 [NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大意就不说了,请看原题。

这道题我在很久之前就A了,昨天朋友问起发现自己还写错了几次,实在惭愧,今天记录一下这个思路。

思路

首先,如果已知撤走的石头,想要求最短距离,是不容易的,但是如果已知最短距离,求“一定要至少撤走多少个石头”可以通过遍历一遍,O(N)的复杂度算出来。

再发现,最短距离和撤走的石头数目是成正相关的,撤走的石头越多,最短的跳跃距离不变或越多,于是可以想到二分法。二分的是最短距离,然后通过最短距离求到至少要撤走多少个石头。

此时去找临界条件,即最短距离再 + 1就会导致撤走的石头也要 + 1这个临界条件。

即check(l) = M,check(r) = M + 1,此时的 l 就是最大的“最短跳跃距离”。

听起来蛮怪的,最大的最短距离,但是确实是这么回事。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 5e4 + 10;

int L, N, M, d[maxn];

int check(int k)//当距离固定为k时,可以撤走多少个石头 
{
	int dist = 0, res = 0;
	for(int i = 1;i <= N; ++ i)
	{
		//如果两点之间距离小于k,即不满足最短距离为k的条件 
		if(d[i] - dist < k)res ++;
		else dist = d[i];
	}
	return res;
}

signed main()
{
	cin >> L >> N >> M;
	for(int i = 1;i <= N; ++ i)cin >> d[i];
	d[++ N] = L;//将终点也存下来,作为第N个点
	int l = 0,r = L + 1;
	while(l + 1 != r)
	{
		//撤走的石头个数和最近跳跃距离成正相关 
		int mid = l + ((r - l) >> 1);
		if(check(mid) <= M)l = mid;
		else r = mid;
	}
	cout << l << '\n';
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 二分 洛谷 算法竞赛 贪心
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号