信奥赛-刷题笔记-二分篇-T2-P1824进击的奶牛0531

原创

IT从业者张某某

修改于 2025-06-01 08:16:31

15200

代码可运行

文章被收录于专栏：信奥赛-刷题笔记信奥赛-刷题笔记

运行总次数：0

代码可运行

总题单

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

二分篇题单

P1824 进击的奶牛

https://www.luogu.com.cn/problem/P1824

题目描述

Farmer John 建造了一个有 N （2 \leq N \leq 10 ^ 5 ) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x _ 1, x _ 2, \cdots, x _ N （0 \leq x _ i \leq 10 ^ 9 ）。

他的 C （2 \leq C \leq N ）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

输入格式

第 1 行：两个用空格隔开的数字 N 和 C 。

第 2 \sim N+1 行：每行一个整数，表示每个隔间的坐标。

输出格式

输出只有一行，即相邻两头牛最大的最近距离。

输入输出样例 #1

输入 #1

输出 #1

代码1

#include <bits/stdc++.h>
using namespace std;
int n,m;
int ans=-1;
int a[1000005];
bool check(int x){   //答案是否满足，满足返回1，反之返回0
    int now = 1, num = 1;
    for (int i = 2; i <= n; i++){
        if (a[i]-a[now]>=x){
            now=i;
            num++;
        }
    }
    return num>=m;
}
void merge(int l,int r){
	if(r-l<0) return;    //边界
	int mid=l+(r-l>>1);    //这样处理防止溢出
	if(check(mid)){   //如果满足，我们记录当前最大值，然后往左区间寻找答案
		merge(mid+1,r);
		ans=max(ans,mid);
	}
	else{  //如果不满足，就往右区间寻找
		merge(l,mid-1);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);  //注意，要排序处理。
	merge(1,(2<<30));
	printf("%d",ans);
}

代码2-二分+贪心

这个问题 —— P1824 进击的奶牛，是经典的 “最大化最小距离”类型问题，可以用 二分答案 + 贪心判断 的方法高效解决。

🧠 一、题目理解

我们有：

N 个隔间（分布在一条直线上），每个隔间的坐标是已知的。
C 头牛要放进这些隔间中，每头牛只能住一个隔间。
要求：任意两头牛之间的距离尽可能大。换句话说，我们要让最近的一对牛之间的距离最大。

🎯 目标：

找出一种安排方式，使得 所有相邻牛之间的最小距离尽可能大。

📌 举个例子

输入样例：

排序后隔间位置为：[1, 2, 4, 8, 9]

我们要选 3 个位置放牛，比如：

1     4     9
↑     ↑     ↑
牛    牛    牛

那么三段距离分别是：3 和 5，其中最小的距离是 3。

如果我们想让这个“最小距离”更大一点，比如变成 4，那还能不能选出 3 个位置？

试试看：

1   4   8   → 距离是 3 和 4 → 最小是 3
1   4   9   → 最小是 3
4   8   9   → 最小是 1

都不行。所以最大可能的“最小距离”就是 3。

🔍 二、解题思路：二分答案 + 贪心判断

✅ 思路总结：

这是一个典型的 最大化最小值 类型的问题，常用策略如下：

🧩 步骤一：排序隔间坐标

因为牛必须放在有序的位置上才能比较它们之间的距离，所以我们第一步要把隔间坐标从小到大排序。

🧩 步骤二：二分搜索答案

我们要找的是最大的“最小距离”，设为 d。

最小可能的 d = 0
最大可能的 d = x[N-1] - x[0]（即最远两个隔间的距离）

在这个范围内进行 二分查找：

l = 0;
r = x[N-1] - x[0];
ans = 0;

while (l <= r) {
    mid = (l + r) / 2;
    if (可以安排 C 头牛，并且每两头之间距离 ≥ mid) {
        ans = mid;
        l = mid + 1; // 尝试更大的距离
    } else {
        r = mid - 1; // 当前太大，尝试更小的距离
    }
}

🧩 步骤三：贪心判断函数（关键）

写一个函数 check(d) 来判断是否可以把 C 头牛放进隔间，且每两头之间的距离至少为 d。

实现逻辑：

第一头牛放在第一个隔间；
然后往后遍历，每次找到距离上一头牛 ≥ d 的下一个隔间；
如果能放满 C 头牛，返回 true；否则返回 false。

bool check(int d) {
    int cnt = 1;         // 已经放了一头牛
    int last = x[0];     // 上一头牛的位置

    for (int i = 1; i < N; ++i) {
        if (x[i] - last >= d) {
            ++cnt;
            last = x[i];
            if (cnt == C) return true;
        }
    }

    return cnt >= C;
}

🧪 三、代码实现（完整版）

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
int N, C;
int x[MAXN];

bool check(int d) {
    int cnt = 1;
    int last = x[0];
    for (int i = 1; i < N; ++i) {
        if (x[i] - last >= d) {
            ++cnt;
            last = x[i];
            if (cnt == C) return true;
        }
    }
    return cnt >= C;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> C;
    for (int i = 0; i < N; ++i) {
        cin >> x[i];
    }

    sort(x, x + N);

    int l = 0, r = x[N - 1] - x[0], ans = 0;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans << '\n';

    return 0;
}

📌 四、时间复杂度分析

排序：O(N logN)
二分查找：最多 30 次（因为 x[N-1] - x[0] ≤ 1e9）
每次检查：O(N)

✅ 总体复杂度：O(N logN + N * log(max_distance)) ≈ O(N logN)，完全可以通过！

🧠 五、类似题目推荐

这类“最大化最小值”的问题还有：

题目	描述
跳石头	删除石头使跳跃距离最小值最大
数列分段 II	分段使各段和最大值最小
运输问题	分车装货，使最大运力最小

✅ 六、总结

内容	说明
类型	二分答案 + 贪心判断
核心思想	在 `[0, max_gap]` 范围内二分搜索最大可能的最小距离
时间复杂度	O(N logN)
关键点	`check()` 函数的设计
应用场景	所有“最大化最小值”或“最小化最大值”类问题

🚀 小技巧优化建议

如果你希望进一步提高性能（特别是在大数据量的情况下），可以加上以下两行代码来加速 IO 操作：

ios::sync_with_stdio(false);
cin.tie(nullptr);

这两个语句会关闭 cin 和 cout 与 scanf/printf 的同步，加快输入输出速度。

如果你还有其他问题，比如想了解底层原理、调试方法、或想把这个程序改成支持多组数据等，也可以继续问我 😊

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;
 
int main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	
	cout<<"Hello NOI"<<endl;
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：

FILE _freopen( const char_ path, const char _mode, FILE_ stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    freopen("7532.in", "r", stdin);
    freopen("7532.out", "w", stdout);
    //原来的代码保持不变
    double a, b, r;
    int k;
    cin >> a >> b;
    k = int(a/b);
    r = a - b * k;
    printf("%g", r);
    //-------------
    fclose(stdin);
    fclose(stdout);
    return 0;
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S13

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S13

登录后参与评论

0 条评论

热度