竹丝码迹

  • 首页
  • 技术分享
    • 流媒体音视频
    • Note
    • Technology
    • System
    • Code
    • Toys
  • 友情链接
    • LeetCode
    • OSCHINA
    • 牛客网
  • 关于博主
纸上得来终觉浅,绝知此事要躬行
  1. 首页
  2. Code
  3. 正文

P2678_跳石头

2019年11月25日 213点热度 0人点赞 0条评论

解题思路

弱弱的写一个二分答案
可以通过二分的思想,判断该 mid 是否可以作为最小距离的最大值,如果可以便更新左边界(最小值最大化)。
那么如何判断是否可以作为最小距离的最大值呢?
这里有一点贪心的思想,可以判断当前点距离上一个点的距离是否大于等于 mid,如果不满足便拿掉该块石头,如果拿掉的石头数量超过 m 个,也说明该 mid 不满足。

code

#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 50005

int arr[MAXN];
int e, n, m;

int check(int x) {
    int last = 0, now, cnt = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] - last < x) {
            if (i == n - 1 || cnt == m) return 0;
            cnt += 1;
        } else {
            last = arr[i];
        }
    }
    return 1;
}

int solve() {
    int l = 0, r = e, mid;
    while (l < r) {
        mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return r;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> e >> n >> m;
    for (int i = 0; i < n; i++) cin >> arr[i];
    arr[n++] = e;
    cout << solve() << endl;
    return 0;
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2019年11月25日

ronnie

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >

文章评论

取消回复
最新 热点 随机
最新 热点 随机
H264基础 YUV入门基础 编解码基础 WebRTC入门 Bat脚本基础入门 只需三步便可下载无水印图片
WebRTC入门H264基础多线程与多进程STL简记C++学习历程基于C语言的Socket编程
剑指offer YUV入门基础 搭建UOJ P1803凌乱的yyy / 线段覆盖 题解代码 hzoj_190_路飞的猜想
分类目录
标签聚合
数学 操作系统 SPFA 离散化 分治 贪心 多重背包 树状数组 素数 动态规划 编解码 单调队列 WebRTC 归并排序
目录
  • 1 解题思路
  • 2 code

COPYRIGHT © 2021 竹丝码迹. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

黑ICP备19006658号