首页 > 其他分享 >[2015年NOIP提高组] 跳石头

[2015年NOIP提高组] 跳石头

时间:2022-08-22 20:00:22浏览次数:60  
标签:NOIP temp 检测 石头 ans 2015

先用二分法谋定一个数,temp_ans = (L + R) / 2; 我们假设这个temp_ans ,就是所有删除方案中,maxn个最小差值中的最大的那个,即答案:ans。

而根据题目要求,我们需要拿掉M个石头。所以,我们要拿着这个temp_ans 去做个检测,检测是否可以在拿走 <= M 个石头的情况下结束检测。

如果可以,则这个temp_ans 大概是某一个方案的最小差值,我们再用二分把temp_ans 放大一点,再去检测。最终结束的二分查找,所得的temp_ans就是答案:ans

 

标签:NOIP,temp,检测,石头,ans,2015
From: https://www.cnblogs.com/zjtofficial/p/16614060.html

相关文章

  • [2015年NOIP提高组] 跳石头
    运用二分策略先写函数确定距离,然后看要搬的石头数满足题意吗。距离确定后,把间距小于确定距离的需要全部搬走。然后向左或向右再找更小或大的距离每次都检查是否能仅移走......
  • 跳石头
    先把跳跃距离二分,然后把这个值作为当前的解,然后用一个check函数判断当前解是否合法,如果合法,那么就去右边继续找,如果不合法,那么就去左边寻找。最主要的就是check函数,可以先......
  • [2015年NOIP提高组] 跳石头
    一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有......
  • 雅礼NOIP2018集训 day5 赛
    雅礼NOIP2018集训day5赛题面由于出题人思维枯竭所以想不出好玩的背景。有n个物品,第i个物品的价格是vi,有两个人,每个人都喜欢n个物品中的一些物品。要求选出正......
  • [NOIP2015 提高组] 跳石头
    题目链接:https://www.luogu.com.cn/problem/P2678试题解析:题目应用了二分答案的思想。二分答案的大致模板,每次都分成两个区间(所有情况下都是左闭右开,包括起始状态),答案过大......
  • 雅礼NOIP2018集训 day3 u
    雅礼NOIP2018集训day3u题面考虑一个\(n*n\)的矩阵\(A\),初始所有元素均为\(0\)。执行\(q\)次如下形式的操作:给定\(4\)个整数\(r,c,l,s\),对于每个满足\(x\in[r,r+l),y\in......
  • [2015年NOIP提高组] 跳石头
    首先将石头位置排个序,以便处理方便。从位置的小到大扫遍所有石头,用一个变量存储上一个跳到的点。第一个与这上一个点的距离大于等于x的石头即是下一个跳到的点。因为我们......
  • [2015年NOIP提高组] 跳石头
     [2015年NOIP提高组]跳石头思路:本题是最大化最小值问题,考虑二分答案解决。先写函数确定距离,然后看要搬的石头数满足题意吗。距离确定了,把间距小于确定距离的需要全部搬......
  • 1033 [NOIP2017]逛公园 记忆化搜索 比最短路长k的方案数 dp递推算方案数
     链接:https://ac.nowcoder.com/acm/contest/26077/1033来源:牛客网题目描述策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有......
  • 4. [2001年NOIP普及组] 最大公约数和最小公倍数问题
    题目链接(码学堂,数据弱)题目链接(洛谷,数据极强)摘要:1.P,Q是正整数(unsigned)2.要求P,Q以x0为最大公约数,以y0为最小公倍数.试求:满足条件的所有可能的两个正整数的个数. ......