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

[2015年NOIP提高组] 跳石头

时间:2022-08-22 19:11:32浏览次数:70  
标签:cnt NOIP int sto 石头 ii 2015 sg zuo

首先将石头位置排个序,以便处理方便。

从位置的小到大扫遍所有石头,用一个变量存储上一个跳到的点。第一个与这上一个点的距离大于等于x的石头即是下一个跳到的点。因为我们要取最优状态,所以要保证跳过的石头数最少。

这样,便求出了这个x是否可行,如果可行,那就往右边二分,但要记得范围要包括x;若不行,则往左边二分,右限制不包括x。然后,二分到左右边界相等,输出即可。

#include<bits/stdc++.h>
using namespace std;
int sto[100000];
int main()
{
int s,n,m;
scanf("%d%d%d",&s,&n,&m);
int zuo=1,you=s,mid;
for(int i=0;i<n;i++)scanf("%d",&sto[i]);
sort(sto,sto+n);
int sg,cnt,ii;
while(zuo!=you)
{
mid=(zuo+you+1)>>1;
sg=cnt=0;
for(ii=0;ii<n;ii++)
{
if(s-sto[ii]<mid)break;
if(sto[ii]-sg<mid)cnt++;
else sg=sto[ii];
}
cnt+=n-ii;
if(cnt<=m)zuo=mid;
else you=mid-1;
}
printf("%d",zuo);
return 0;
}

标签:cnt,NOIP,int,sto,石头,ii,2015,sg,zuo
From: https://www.cnblogs.com/wangjunlong9948/p/16613912.html

相关文章

  • [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为最小公倍数.试求:满足条件的所有可能的两个正整数的个数. ......
  • [2015年NOIP普及组] 金币
    #include<iostream>intmain(){intstep=1;intcoin=1;intnow;std::cin>>now;intcount=0;intwalk=0;for(intday=1;day<=now;da......
  • 3. [2011年NOIP提高组] 铺地毯
    题目链接本题精彩所在:数据范围数据范围是x,y分别到达了100000,开二维数组无疑会空间爆炸因此,我们可以通过他给予的坐标范围(围成一个四边形)通过逆序判断坐标是否越界,来做......
  • [NOIP2001 提高组] 一元三次方程求解
    [NOIP2001提高组]一元三次方程求解题目描述:这道题就是一道简单的暴力枚举,做的时候要注意一下double精度,当然用二分做的话肯定会更好(虽然我也不会)代码如下:#include<......
  • [2001年NOIP普及组] 最大公约数和最小公倍数问题
    p*q等于x0*y0。可以枚举到x0*y0中能被x0*y0整除的数,如果这个数与另一个这个数与它的积是x0*y0的数的最大公因数是x0或最小公倍数是y0,那这个数不是p就是q。每枚举出这样一个......
  • 2. [NOIP2001 提高组] 一元三次方程求解
    试题描述:输入一行,4个实数a,b,c,d输出一行,3个实根,从小到大输出,并精确到小数点后2位。样例输入1-5-420样例输出-2.002.005.00错误代码如下(会没有......
  • P1008 [NOIP1998 普及组] 三连击
    P1008[NOIP1998普及组]三连击 题目描述:将1,2,…,9共9个数分成3组,分别组成3个三位数,且使这3个三位数构成1:2:3的比例,试求出所有满足条件的3个三位数。这道......
  • 4. [2003年NOIP普及组] 乒乓球!!!!(有疑惑)
    【问题描述】华华通过以下方式进行分析,首先将比赛每个球的胜负列成一张表,然后分别计算在11分制和21分制下,双方的比赛结果(截至记录末尾)。比如现在有这么一份记录,(其中W表示......