草庐IT

「二分」愤怒的牛

孤星·璀璨 2023-03-28 原文

本题为1月12日22寒假集训每日一题题解

题目来源:USACO 2005 Feb. Gold

题面

题目描述

农夫约翰建造了一座有n间牛舍的小屋，牛舍排在一条直线上，第i间牛舍在 $ x_i $ 的位置，但是约翰的m头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

输入

第一行用空格分隔的两个整数n和m；

第二行为n个用空格隔开的整数，表示位置xi。

输出

输出仅一个整数，表示最大的最小距离值。

样例输入

5 3
1 2 8 4 9

样例输出

3

提示

样例解释:

把牛放在 11, 44 ,88 这样最小距离是 33 。

数据范围:

$ 2 \leq n \leq 10^5 $ , $ 0 \leq x_i \leq 10^9 $ , $ 2\leq m \leq n $。

思路分析

此题题面有点绕,总而言之就是让你最大化最近两头牛之间的距离,显然,这是一个最大化最小值的问题,可以通过二分法来解决.

此处要使用二分法,我们的一个核心问题是,对于给出的一个最近两头牛之间的距离,我们要怎么判断它是否成立.

注意到这里牛舍之间的距离只能取得某几个值,在整数上并不一定是连续取的,且我们最终求的是最大值,所以我们并不需要判断能不能严格取得这个值,而是只需要判断能否使得最近的两头牛之间的距离不小于这个值,即能否使得任意两头牛之间的距离均不小于这个值.

所以我们只需要将牛舍排序,从第一个牛舍开始安排牛,然后找其后不小于给定距离的最近的牛舍,在其中安排下一头牛,接着继续如法炮制找下一个牛舍.如果在安排完所有牛之前已经无牛舍可用,则可知这个距离不成立,即这个距离太大,我们将二分区间大的一半砍掉;反之则是成立,我们将二分区间小的一半砍掉,去寻找更大的距离.

参考代码

我个人习惯二分的区间是两端都闭的,而不是常规的左闭右开,所以二分部分缩小区间的方式以及最后的输出可能会与普遍写法不同.

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    int *x = new int[n]; // 牛舍
    for (int i = 0; i < n; i++)
    {
        cin >> x[i];
    }

    sort(x, x + n); // 使牛舍按坐标排序

    // 二分
    int l = 0, r = 1000000000, mid;
    while (r >= l)
    {
        int mid = l + ((r - l) >> 1);

        // 判断当前的距离能否被满足
        bool flag = true;
        int prev = 0;                // 从第一个牛舍开始
        for (int i = 1; i < m; i++) // 第一个牛舍安置了第一头牛,所以只需要继续安置m-1头牛即可
        {
            // 找其后不小于给定距离的最近的牛舍
            int crt = prev + 1;
            while (crt < n && x[crt] - x[prev] < mid)
            {
                crt++;
            }

            // 在安排完所有牛之前已经无牛舍可用,则可知这个距离不成立
            if (crt >= n)
            {
                flag = false;
                break;
            }

            prev = crt; // 更新前一个牛舍的位置
        }

        if (flag) // 当前距离能被满足,尝试寻找更大
        {
            l = mid + 1;
        }
        else // 当前距离太大,不能被满足,将大的一半区间砍掉
        {
            r = mid - 1;
        }
    }

    cout << r << "\n"; // 区间不存在时,原本的右指针(此时在左侧)指向的即是最大的可行距离

    delete x;
    x = nullptr;
    return 0;
}

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德

二分愤怒牛舍头牛算法与数据结构

有关「二分」愤怒的牛的更多相关文章

  1. 常见搜索模板DFS+BFS+二分搜索【算法】 - 2

     本篇讲的是常见的搜索模板，搜索题的解法时比较固定的，只要把模板记熟，加上自己找几道习题练习体会后，相信各位下次遇到这类题一定能拿下！！下面我将已典型的题目为例子介绍几种常见的搜索方式。 1.二分搜索二分搜索代码模板：例题：#includeusingnamespacestd;doublen;constdoubleeps=1e-12;//二分搜索intmain(){ intt; cin>>t; while(t--){ cin>>n; doublel=0,r=100000,res=-1; while(ln)r=mid-0.0001; elseif(mid*mid*mid二分搜索是只能对有

  2. day1-数组part01| 704. 二分查找、27. 移除元素 - 2

    数组理论基础数组是存放在连续内存空间上的相同类型数据的集合。数组下标从0开始数组内存空间的地址是连续的c++中vector和array的区别1、vector是顺序容器，其利用连续的内存空间来存储元素，但是其内存空间大小是能够改变的。2、array是顺序容器，其也是利用连续的内存空间来存储元素，但它的内存空间是固定大小的，申请之后就无法改变。3、vector的底层是array实现的二维数组二维数组在内存的空间地址是连续的704|二分查找思路1、把整个数组一分为二；2、判断目标值在左区间还是右区间，若在左区间，则修改右区间指针的位置；若在右区间，则修改新区间的左区间位置3、重复上述过程，直到lef

  3. javascript - 如何开始在 Chrome 上制作像愤怒的小鸟这样的游戏 - 2

    http://chrome.angrybirds.com/据说基于浏览器的应用程序是使用Canvas2D或WebGL完成的。我尝试使用“检查元素”按钮使用chrome查看源代码，但我的chrome每次都会崩溃。我只是想了解如何开始开发如此出色的游戏。为初学者寻找在线资源、书籍和特定提示的指针。 最佳答案 如果你想要一本书，FoundationHTML5Canvas:ForGamesandEntertainment刚出来。它相当基础，但如果您是JavaScript和Canvas的新手，将会对您有用。节奏更快的介绍是MozillaCan

  4. javascript - 愤怒的小鸟使用什么 javascript 混淆？ - 2

    愤怒的小鸟在chrome网上商店(http://chrome.angrybirds.com)上线他们的javascript代码被混淆了，这似乎比我迄今为止看到的任何js混淆都要好。我想知道是否有人知道他们使用什么或知道类似的东西。 最佳答案 它似乎最初是用GWT编写的——这是有道理的，因为有一个运行在Android上的版本可能是用Java编写的...然后在高级模式下使用闭包编译器进行优化(GWT支持)。编辑:糟糕!不是高级模式。闭包编译器的高级模式未优化输出。例如，诸如“null”之类的符号不会像在闭包混淆程序中那样使用别名。此外，

  5. 【小游戏】Unity游戏愤怒的足球（小鸟） - 2

    目录1.弹弓逻辑2.鸟的逻辑3.GameManager主逻辑文末有源工程地址难度系数： ★★★★☆游戏玩法： 愤怒的足球，其实就是经典的愤怒的小鸟换图项目简介：功能完善，主要代码逻辑完整本文内容： 记录一下这个工程，对内部代码逻辑没有深入了解有待以后发掘1.弹弓逻辑弹弓的逻辑稍微复杂一些，特别是对角度和预制方向绘制线逻辑下面是弹弓里面需要提前声明的一些变量

  6. 数学建模十大算法04—图论算法（最短路径、最小生成树、最大流问题、二分图） - 2

    文章目录一、最短路径问题1.1两个指定顶点之间的最短路径1.1.1Dijkstra算法1.1.2Matlab函数1.2每对顶点之间的最短路径1.2.1Dijkstra算法1.2.2Floyd算法1.2.3Matlab函数二、最小生成树问题2.1Kruskal算法2.2Prim算法三、网络最大流问题3.1网络流问题基础3.2Ford-Fulkerson算法3.3Edmonds-Karp算法3.4Dinic's算法3.5最小割问题（Min-Cut）3.5.1S-TCut3.5.2★最大流-最小割定理（Max-FlowMin-CutTheorem）3.5.3**寻找最小割的方法**四、二分图一、最短

  7. 代码随想录算法训练营第一天 704 二分查找、27 移除元素 - 2

    代码随想录算法Day1|704.二分查找、27.移除元素Lasteditedtime:April5,202311:27AM数据理论基础数组是存放在连续内存空间上的相同类型数据的集合。数组下标都是从0开始的。数组内存空间的地址是连续的数组元素不能删除，只能覆盖C++中二维数组的内存的空间地址是连续的704.二分查找二分法前提：数组为有序数组，且数组中无重复元素循环不变量：对区间的定义应该是一个不变量，在边界处理中应该遵循统一原则左闭右闭：classSolution{public:intsearch(vectorint>&nums,inttarget){intleft=0;intright=num

  8. 【查找算法】二分查找(C# + 递归、非递归和变种形式) - 2

    【查找算法】二分查找(C#+递归、非递归和变种形式)写在前面：本文主要介绍二分查找算法，通过图片解析每一次查找的情况。代码通过C#实现，分别有递归、非递归和变种三种形式。其中变种主要解决数组出现重复数据的问题。最后，我们还分析了二分查找的局限性。活动地址：CSDN21天学习挑战赛本文关键字：经典算法、查找算法、二分查找、图解、C#文章目录【查找算法】二分查找(C#+递归、非递归和变种形式)一、算法效率1.时间复杂度2.空间复杂度二、查找算法1.顺序(线性)查找2.二分查找/折半查找3.插值查找4.斐波那契查找三、算法实践1.图解算法原理2.算法实现非递归实现递归实现3.二分查找变种3.时间复杂

  9. 二分图（概念、相关算法和题目应用）(全面整理) - 2

    TP二分图的概念：二分图常用算法：染色法（判断一个图是否为二分图）：匈牙利算法（求出二分图的最大匹配数）：相应题目应用：二分图染色应用：Acwing：关押罪犯二分图最大匹配应用：Acwing：棋盘覆盖洛谷：矩阵游戏二分图最大匹配的一些推论：二分图最小点覆盖应用：Acwing：机械任务Acwing：泥地二分图最大独立集应用：Acwing：骑士放置二分图最大路径点覆盖与最大路径重复点覆盖应用：Acwing：捉迷藏二分图的概念：二分图通常针对无向图问题（有些题目虽然是有向图，但一样有二分图性质）在一张图中，如果能够把全部的点分到两个集合中，保证两个集合内部没有任何边，图中的边只存在于两个集合之间，这

  10. 新冠肺炎胸部 CT 基于3D-CNN实现二分类 - 2

    新冠肺炎胸部CT基于3D-CNN实现二分类作者:WangXi2016日期:2022.10.27摘要:本示例教程使用3DCNN实现CT数据二分类。1、介绍本示例将展示构建3D卷积神经网络（3DCNN），以预测电子计算机断层扫描（CT）是否感染新冠病毒肺炎。2DCNN通常用于处理RGB图像（3个通道）。3DCNN：它将3D数据或2D帧序列（例如CT扫描中的切片）作为输入，这个架构可以从3D深度或者连续视频帧中产生多通道的信息，然后在每一个通道都分离地进行卷积和下采样操作。最后将所有通道的信息组合起来得到最终的特征描述。2、解压数据集完整数据集链接：https://www.medrxiv.org/c

随机推荐