关键词：
思路：把检验的函数说一下，就是检测的距离x时，是否存在c个隔断相离大于等于x，如果是则返回1，不是则返回0
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int maxn = 1e5 + 10; int a[maxn], n, c, minn=0x3f3f3f3f, ans, mid; bool check(int x) int sum = 0, base = a[1]; for (int i = 2; i <= n; ++i) if (a[i] - base >= x) sum++, base = a[i]; if (sum >= c)return 1; if (sum + 1 < c)return 0; return 1; void half() int l = minn, r = a[n] - a[1]; while (l <= r) mid = (l + r) >> 1; if (check(mid)) l = mid + 1; else r = mid - 1; ans = r; int main() scanf("%d%d", &n, &c); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); sort(a + 1, a + n + 1); for (int i = 2; i <= n; ++i) minn = min(minn, a[i] - a[i - 1]); half(); //二分 cout << ans << endl;
p1824进击的奶牛（二分）(代码片段)
思路：把检验的函数说一下，就是检测的距离x时，是否存在c个隔断相离大于等于x，如果是则返回1，不是则返回0#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintmaxn=1e5+10;inta[maxn],n,c,minn=0x3f3f3f3f,ans,mid;boo... 查看详情
洛谷p1824进击的奶牛题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=1824题目描述FarmerJohn建造了一个有N(2<=N<=100,000)个隔间的牛棚，这些隔间分布在一条直线上，坐标是x1,...,xN... 查看详情
acwing1945.奶牛棒球（枚举+二分）(代码片段)
题目链接https://www.acwing.com/problem/content/1947/思路因为第三头牛和第二头牛的间距是在[2Y-X,3Y-2x]以内的，所以我们可以对第三头牛进行二分搜索，然后将得到的左右区间长度的贡献加在ans上面，详情请看代码代码#include&l... 查看详情
poj2112optimalmilking(二分+最短路+最大流)(代码片段)
<题目链接>题目大意： 有K台挤奶机和C头奶牛，都被视为物体，这K+C个物体之间存在路径。给出一个(K+C)x(K+C)的矩阵A，A[i][j]表示物体i和物体j之间的距离，有些物体之间可能没有直接通路。 每台挤奶机可以容纳m头奶... 查看详情
luogup1824进击的奶牛
题目描述FarmerJohn建造了一个有N(2<=N<=100,000)个隔间的牛棚，这些隔间分布在一条直线上，坐标是x1,...,xN(0<=xi<=1,000,000,000)。他的C(2<=C<=N)头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛... 查看详情
optimalmilking（poj2112+二分+dinic）(代码片段)
...：http://poj.org/problem?id=2112题目：题意：有k台挤奶机，c头奶牛，每台挤奶机每天最多生产m的奶，给你每个物品到其他物品的距离（除了物品到自己本省的距离为0外，两者之间没有路线直接到达也为0，此时需要将距离处理为inf）... 查看详情
p2402奶牛隐藏二分最大流(代码片段)
题目背景这本是一个非常简单的问题，然而奶牛们由于下雨已经非常混乱，无法完成这一计算，于是这个任务就交给了你。(奶牛混乱的原因看题目描述)题目描述在一个农场里有 nn 块田地。某天下午，有一群牛在田地里... 查看详情
二分图最大匹配(代码片段)
...;每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每... 查看详情
二分图最大匹配(代码片段)
...;每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每... 查看详情
p2402奶牛隐藏(二分&网络流)(代码片段)
P2402奶牛隐藏(二分&网络流)最大值最小，考虑二分。对于某个ttt如何判断有解？预处理任意两点最短路(floyd)，然后跑网络流。所有≤t\\let≤t的边容量设为无穷，然后ststst连牛，ededed连牛棚，容量就是对... 查看详情
poj2112///最大流+floyd+二分(代码片段)
题目大意：有k台挤奶机和c头奶牛每台挤奶机最多为m头奶牛服务给定所有挤奶机和奶牛两两之间的距离求一种分配使得奶牛与挤奶机之间的最远距离最小化 floyd求得所有挤奶机与奶牛两两之间的最短距离二分一个最远距离M建... 查看详情
poj--2456(代码片段)
...互攻击到。思路： 这题也是设计到了最大化问题，即奶牛之间两两距离最大，可以考虑二分查找的思路 同样的这题也要考虑一下贪心策略，要把奶牛先安置在比较靠前的牛舍中 首先第0个宿舍肯定要入住奶牛的，所... 查看详情
10:河中跳房子(二分）(代码片段)
描述每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1≤ L≤1,000,000,000)的终点处均有一个岩石。在起点... 查看详情
luogup1843奶牛晒衣服(代码片段)
模拟T1，贪心+排序或者二分都行贪心策略很好想，显然每次晒耗时最久的衣服最优，问题是要在每次晒完后都再次找到耗时最久的衣服，不能每次都sort，所以单调队列或者大根堆二分也不难，直接二分时间，筛一遍衣服统计需... 查看详情
p1843奶牛晒衣服(代码片段)
...坑点是，你可能减出来个负数----------------------------------奶牛为什么要穿衣服---------------------------------#include<iostream>usingnamespacestd;longlongl,r;longlongn,a,b;longlongw[500001];boolc(longlongk)longlongcnt=0;for(longlongi=1;i<=n;++i)longlongv=w[i]-a*k;if(v... 查看详情
poj2112optimalmilking（二分+最大流）
POJ2112OptimalMilking题目链接题意：给定一些机器和奶牛，在给定距离矩阵，（不在对角线上为0的值代表不可达），每一个机器能容纳m个奶牛。问全部奶牛都能挤上奶，那么走的距离最大的奶牛的最小值是多少思路：明显的二分+最... 查看详情
二分查找：一种效率较高的查找方法(代码片段)
...《二分查找-一种效率较高的查找方法》，作者：i进击的攻城狮。一、二分查找概述二分查找是一种相比于逐个查找，性能更加优秀，时间复杂度更低的一种算法。二分查找的思路是，对一个顺序的集合 查看详情
p1843奶牛晒衣服（二分）(代码片段)
思路：就是一个模板，只是找最小化而已。在判断函数里面：当湿度<=x*A不判断，反之sum+=(a[i]-x*A)/B+(a[i]-x*A)%B?1:0;#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;constintmaxn=5e5+10;inta[maxn],n,A,B,maxx,ans,mid;boolcheck(i... 查看详情