关键词:
P1316 丢瓶盖
题目描述
陶陶是个贪玩的孩子,他在地上丢了A个瓶盖,为了简化问题,我们可以当作这A个瓶盖丢在一条直线上,现在他想从这些瓶盖里找出B个,使得距离最近的2个距离最大,他想知道,最大可以到多少呢?
输入输出格式
输入格式:第一行,两个整数,A,B。(B<=A<=100000)
第二行,A个整数,分别为这A个瓶盖坐标。
输出格式:仅一个整数,为所求答案。
输入输出样例
5 3 1 2 3 4 5
2
说明
限时3秒
P1824 进击的奶牛
题目描述
Farmer John建造了一个有N(2<=N<=100,000)个隔间的牛棚,这些隔间分布在一条直线上,坐标是x1,...,xN (0<=xi<=1,000,000,000)。
他的C(2<=C<=N)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,Farmer John想把这些牛安置在指定的隔间,所有牛中相邻两头的最近距离越大越好。那么,这个最大的最近距离是多少呢?
输入输出格式
输入格式:第1行:两个用空格隔开的数字N和C。
第2~N+1行:每行一个整数,表示每个隔间的坐标。
输出格式:输出只有一行,即相邻两头牛最大的最近距离。
输入输出样例
5 3 1 2 8 4 9
3
【题解】
二分答案
从第一个开始贪心放即可,证明显然
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 7 inline void read(int &x) 8 { 9 x = 0;char ch = getchar(), c = ch; 10 while(ch < ‘0‘ || ch > ‘9‘)c = ch, ch = getchar(); 11 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar(); 12 if(c == ‘-‘)x = -x; 13 } 14 15 const int MAXN = 100000 + 10; 16 17 int n,num[MAXN],m,ans; 18 19 bool check(int k) 20 { 21 int pre = 1, cnt = 1; 22 for(register int i = 2;i <= n;++ i) 23 if(num[i] - num[pre] >= k)++ cnt, pre = i; 24 if(cnt >= m)return 1; 25 return 0; 26 } 27 28 int main() 29 { 30 freopen("data.txt", "r", stdin); 31 read(n);read(m); 32 for(register int i = 1;i <= n;++ i) 33 read(num[i]); 34 std::sort(num + 1, num + 1 + n); 35 register int l = 1, r = num[n] - num[1],mid; 36 while(l <= r) 37 { 38 mid = (l + r) >> 1; 39 if(check(mid))l = mid + 1, ans = mid; 40 else r = mid - 1; 41 } 42 printf("%d", ans); 43 return 0; 44 }
洛谷的uid是啥
参考技术A洛谷的uid是创建账户的时候用来识别身份的一串代码,用来加好友等作用,是一个人在洛谷这个软件身份的象征。 查看详情
洛谷有人疯了!!!
洛谷名人几年前经典案例总结:作了不一定会死,但死了一定是作的!!! 查看详情
题解目录
洛谷题解:P3399【丝绸之路】洛谷题解:P2364【胖男孩】洛谷题解:P1020【导弹拦截】洛谷题解:P1160【队列安排】洛谷题解:P1004【方格取数】 查看详情
洛谷洛谷月赛4月月赛round1/2
洛谷月赛“月”来“月”丧了,一月更比一月丧,做得我十分不“月”……4月的两轮月赛,都只会T1,就写一下吧,等待后续更新……先看看Round1的T1:【R1T1】网址:点我【题意简述】给定一个长度为n的序列,其中的元素均是1~... 查看详情
每周刷题记录--bynoble_
...-------------------------------------2017.10.3主要是水题与傻逼dp:洛谷P1199三国游戏模拟洛谷P1115最大子段和dp洛谷P1508Likecloud-吃、吃、吃洛谷P1510精卫填海洛谷P1855榨取kkksc03洛谷P1982小朋友的数字洛谷P1981表达式求值洛谷P 查看详情
洛谷p3379lca,hdu2586,洛谷p1967货车运输,倍增lca,树上倍增
倍增lca板子洛谷P33791#include<cstdio>2structE3{4intto,next;5}e[1001000];6intf1[500100],anc[500100][20],log2n,deep[500100],n,m,s,ne;7boolvis[500100];8voiddfs(intx,intfa)9{10inti,k;11vis[x]=1;12anc[x][0 查看详情
洛谷题目怎么看答案
洛谷题库是在最右边竖着的工具栏的第二个图标。点进去就是洛谷的题库了在这里可以搜题目。也可以搜题号。或者是算法。在题目的前边会有三个符号,第一个是绿√第二个是红叉子第三个是灰色的短横线分别表达:满分,错误(... 查看详情
洛谷1948电话线
题目描述FarmerJohnwantstosetupatelephonelineathisfarm.Unfortunately,thephonecompanyisuncooperative,soheneedstopayforsomeofthecablesrequiredtoconnecthisfarmtothephonesystem.ThereareN(1≤N≤1,000)forlorntelep 查看详情
洛谷t3401洛谷树树剖&&分治
这道题好干燥啊。。。折腾了半个月。。。感谢bogo大佬对我的指导。。。题目要求支持的操作:1.查询某段路径的所有子路径的xor值之和;2.修改某条边的权值。重点是操作1。刚开始,我看到了操作1之后就不自觉的想到了非~常... 查看详情
我的洛谷题解
2018.2.4P1217【USACO1.5]回文质数PrimePalindromes】2018.2.6 P1308【统计单词数】链接持续更新中 查看详情
洛谷p1055isbn号码
参考技术A注意对X的处理 查看详情
洛谷p1471方差
...方差。 ——by 洛谷;http://www.luogu.org/problem/show?pid=1471《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《 查看详情
洛谷p1855榨取kkksc03
题目描述洛谷2的团队功能是其他任何oj和工具难以达到的。借助洛谷强大的服务器资源,任何学校都可以在洛谷上零成本的搭建oj并高效率的完成训练计划。为什么说是搭建oj呢?为什么高效呢?因为,你可以上传私有题目,团... 查看详情
洛谷p1432倒水问题(codevs.1226)
To洛谷.1432倒水问题题目背景Inthemovie"DieHard3",BruceWillisandSamuelL.Jacksonwereconfrontedwiththefollowingpuzzle.Theyweregivena3-gallonjuganda5-gallonjugandwereaskedtofillthe5-gallonjugwithexactly4gallons.This 查看详情
洛谷2484return
好像1for(inti=1;i<=n;i++){2printf("%d ",i);3return0;4 }和1 for(inti=1;i<=n;i++){2 return0,printf("%d ",i);3 }是一样的。调题洛谷2484时,发现似乎是这样的。这样可以过样例但是,去掉return后面的printf之后,就变成了 &n 查看详情
洛谷——修复公路
按照时间排序,逐个unite。#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintmaxn=1010;structedge{intx,y,t;}a[100010];intn,m,fa[maxn],cnt;voidinit(){for(inti=1;i< 查看详情
洛谷2615
朴素的暴力膜。。把规则翻译为代码即可详见注释上代码~#include<stdio.h>usingnamespacestd;intlastx;intlasty;intmap[39][39];intn;voidprit()//打印函数{for(inti=0;i<n;i++){for(intj=0;j<n;j++){printf("%d",map[i][j]);}printf(" 查看详情
洛谷是啥?
洛谷是基于网页形式的信息学在线评测系统。同时具有多种社区功能。简 介洛谷创办于2013年,出道名为“洛谷OnlineJudge”,致力于为oiers/acmers提供清爽、快捷的编程体验。它不仅仅是一个在线测题系统,它拥有强大的社区、... 查看详情