---
title: "赶牛入圈"
created: 2025-11-28
tags:
  - 算法
---

# 赶牛入圈

## 题目 [赶牛入圈](https://www.acwing.com/problem/content/description/123/)

![[image-33bf48a6.png]]

## 思路分析

模型可以抽象成：

![[image-63cbe8f7.png]]

要找到最小的一个方框 让它里面包含C个草

我们怎么快速得知一个方框里有几个草呢？

很明显 二维前缀和 利用$s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]$就能求出来

![[image-e2a4b8bc.png]]

那么我们就把所有的草 构造出一个前缀和数组

但是发现

![[image-49b172ca.png]]

范围在1~10000之间 这要构造的话 就得$10000^2$显然不行

而点的范围只有500 （只有$500^2$个草）

![[image-26a69ef3.png]]

那么我们就可以使用离散化 把这500个有意义的数据映射在一个小的二维数组里面

再对这个新数组进行前缀和操作

对于找到最小边长 看到关键词最小 不难想到用二分去找答案

给定一个mid边长 去前缀和数组中以这个大小遍历一遍 看是否有满足条件的（有C个草）

如果有 说明我们这个mid可能取大了 也可能刚好取到 所以r=mid

如果没有 说明 mid取小了 l=mid+1 所以为模版1

这个边长不外乎就是取大了取小了 显然具有二段性 所以二分是可行的

这个check中的遍历过程 实际上是用到了双指针 右边和下面（x2和y2）不断右探 当不满足条件时（x2到x1的距离大于给定的mid长度时）x1、y1才++
这里有个注意点就是 我们用的是离散化后的点算距离 所以x2和x1 y2和y1之间的距离不是x2-x1和y2-y1 而是我们真实数组里面的距离
需要用alls[x2]-alls[x1+1]+1 和alls[y2]-alls[y1+1]+1来算

有三个问题 依次来进行解释

首先为什么用alls

![[image-9f5bab7a.png]]

离散化后是把两个有意义的点映射在新下标处 他们真实的距离可并不是新下标去做减法计算 而是要用离散化前的真实数组的下标去做计算 而真实下标存在哪里呢
对 在alls里面

第二 为什么用alls[x2]-alls[x1+1]+1 和alls[y2]-alls[y1+1]+1 这里要加上个1？

这是双指针尺取法的一个细节问题 意思是 如果我下一个点不满足状态了 我就要更新左边的指针了 而不是我已经不满足了才更新 具体了解 去刷双指针

第三 为什么用alls[x2]-alls[x1+1]+1 和alls[y2]-alls[y1+1]+1 这里又要加1？

不妨转为一维来看

![[image-9d7f9234.png]]

因为草不是一个点 而是一个块 它是有单位长度的

所以要把x1包含进来 应该还得加上个1

最后回过头来考虑判定问题

一个范围里是否有≥C个草 满足true 否则false

既然前面有边界细节要扣 这里应该也有

还是如上图所示 要包含x1这块草 得加1

所以对于原公式的$s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]$

y1-1和x1-1是完全没必要的

因为x1 y1本身就没取到那一块

所以公式变成  $if(s[x2][y2]-s[x1][y2]-s[x2][y1]+s[x1][y1]>=C)$

这样一来这道题就解决了

会发现涉及的东西真多啊 二维前缀和 二分 离散化 双指针 枚举……虽然也都是基本功

还有一大堆细节要扣

真的好 这题（但别出现在赛场上 hh）

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef pair<int,int> PII;
const int N=1010;
PII point[N];
vector<int> alls;
int s[N][N];
int n,C;

int find(int k){
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]>=k)    r=mid;
        else    l=mid+1;
    }
    return r;
}

bool check(int len){
    for(int x1=0,x2=1;x2<alls.size();x2++){
        while(alls[x2]-alls[x1+1]+1>len)
            x1++;
        for(int y1=0,y2=1;y2<alls.size();y2++){
            while(alls[y2]-alls[y1+1]+1>len)
                y1++;
            if(s[x2][y2]-s[x1][y2]-s[x2][y1]+s[x1][y1]>=C)
                return true;
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>C>>n;
    alls.push_back(0);//为了从1开始做前缀和 先放个0占位
    for(int i=0;i<n;i++){
        int x,y;cin>>x>>y;
        point[i]={x,y};
        alls.push_back(x);
        alls.push_back(y);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(int i=0;i<n;i++){
        int x=find(point[i].first),y=find(point[i].second);
        s[x][y]++;
    }
    for(int i=1;i<alls.size();i++){
        for(int j=1;j<alls.size();j++){
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }

    int l=1,r=10000;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))  r=mid;
        else    l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[蛋糕游戏|蛋糕游戏]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/前缀和与差分相关模型/前缀和/餐厅|餐厅]]