洛谷p1824进击的奶牛题解

关键词：

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。

题目链接 ：https://www.luogu.org/problem/show?pid=1824

5 3
1 
2 
8 
4 
9 
 

3


分析：
对最大的最近距离进行二分，判断能否符合要求。
大概算是二分答案的裸题？

AC代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<iostream>
 5 
 6 using namespace std;
 7 int l = 21474836,r,n,c;
 8 int num[100005];
 9 
10 int cmp(int a,int b)
11 {return a < b;}
12 
13 inline void read(int &x)
14 {
15     char ch = getchar(),c = ch;x = 0;
16     while(ch < ‘0‘ || ch > ‘9‘) c = ch,ch = getchar();
17     while(ch <= ‘9‘ && ch >= ‘0‘) x = (x<<1)+(x<<3)+ch-‘0‘,ch = getchar();
18     if(c == ‘-‘) x = -x;
19 }
20 
21 bool jud(int x)
22 {
23     int cnt = 1,tmp = num[1];
24     for(int i = 2;i <= n;++ i)
25     {
26         if(num[i] - tmp >= x)
27             cnt ++,tmp = num[i];
28         if(cnt >= c) return true;
29     }
30     return false;
31 }
32 
33 int main()
34 {
35     read(n),read(c);
36     for(int i = 1;i <= n;++ i)
37     {
38         read(num[i]);
39         if(num[i] > r) r = num[i];
40         if(num[i] < l) l = num[i];
41     }
42     sort(num+1,num+1+n,cmp);
43     while(l+1 < r)
44     {
45         int mid = ((l+r)>>1);
46         if(jud(mid)) l = mid;
47         else r = mid;
48     }
49     printf("%d
",l);
50     return 0;
51 }

p1824进击的奶牛(代码片段)

题目大意：    将c个奶牛放入n个隔间，一直隔间的坐标，问如何放才能使奶牛相邻的距离的最小值最大。(0<=xi<=1,000,000,000)(2<=N<=100,000)。思路：     显然是二分答案，主要是分好后的验证... 查看详情

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... 查看详情

洛谷1578：[wc2002]奶牛浴场——题解(代码片段)

https://www.luogu.org/problemnew/show/P1578#sub由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个... 查看详情

洛谷p2341[haoi2006]受欢迎的牛题解

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=2341题目描述每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自... 查看详情

[wc2002][洛谷p1578]奶牛浴场

洛谷题解里那个人可真是话多呢。 题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛... 查看详情

洛谷p1472奶牛家谱cowpedigrees

 P1472奶牛家谱CowPedigrees102通过193提交题目提供者该用户不存在标签USACO难度普及+/提高 提交  讨论  题解  最新讨论暂时没有讨论题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个... 查看详情

洛谷p1828香甜的黄油sweetbutter题解

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=1828题目描述农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=... 查看详情

洛谷p2676超级书架题解(代码片段)

题目传送门题目一看就是贪心。C++福利来了：sort。基本思路就是：要使奶牛最少那么肯定高的奶牛先啦。直接排序一遍（从高到矮）然后while，搞定！#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llN,B,H[20010];boolcmp(intx,inty)retur... 查看详情

洛谷p1316p1824

 P1316丢瓶盖题目描述陶陶是个贪玩的孩子，他在地上丢了A个瓶盖，为了简化问题，我们可以当作这A个瓶盖丢在一条直线上，现在他想从这些瓶盖里找出B个，使得距离最近的2个距离最大，他想知道，最大可以到多少呢？输入... 查看详情

luogup1824进击的奶牛

题目描述FarmerJohn建造了一个有N(2<=N<=100,000)个隔间的牛棚，这些隔间分布在一条直线上，坐标是x1,...,xN(0<=xi<=1,000,000,000)。他的C(2<=C<=N)头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛... 查看详情

bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)

【题解】　　很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。　　我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。　　显然选择它的儿子... 查看详情

洛谷p1547outofhay题解

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=1547题目背景奶牛爱干草题目描述Bessie计划调查N(2<=N<=2,000)个农场的干草情况，它从1号农场出发。农场之... 查看详情

洛谷p2733家的范围homeontherange

P2733家的范围HomeontheRange• o 26通过o 61提交• 题目提供者该用户不存在• 标签USACO• 难度普及+/提高提交讨论题解最新讨论• 暂时没有讨论题目背景农民约翰在一片边长是N(2<=N<=250)英里的正方形牧场上放牧他的奶... 查看详情

洛谷p2853[usaco06dec]cowpicnics题解(代码片段)

题目连接：https://www.luogu.com.cn/problem/P2853题意：有n个奶牛在不同牧场，牧场之间有m条路。求所以奶牛都能共同到达的牧场的数量思路：dfs每一个奶牛可以到的牧场。开一个d[N]数组记录d[i]i这个牧场能来的奶牛的个... 查看详情

洛谷p1578奶牛浴场

P1578奶牛浴场题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产... 查看详情

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没... 查看详情