洛谷P1316 丢瓶盖

素颜马尾好姑娘i 2022-05-29 08:17 114阅读 0赞

## 题目描述 ##

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

## 输入输出格式 ##

输入格式：

第一行，两个整数，A,B。（B<=A<=100000）

第二行，A个整数，分别为这A个瓶盖坐标。

输出格式：

仅一个整数，为所求答案。

## 输入输出样例 ##

输入样例\#1： 复制

5 3
    1 2 3 4 5

输出样例\#1： 复制

2

## 说明 ##

限时3秒

思路：先排序

左边界为l=1，r=f\[A\]-f\[1\]

然后二分答案，当前的坐标大于基准事就sum++，同时基准也要变一下。当sum>=B时说明mid较小，否则mid较大

感觉二分的题这些分解把卧的有点难度。尤其时check函数里面的。

#include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int f[100006];
    int A, B;
    int Max;
    int x;
    
    bool check(int mid)
    {
    	int sum = 1;
    	int p = 1;
    	for (int i = 2; i <= A; i++)
    	if (f[i] - f[p]>=mid) 
    	 { sum++, p = i; }
    	if (sum >= B)
    		return true;
    	else
    		return false;
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> A >> B;
    
    	for (int i = 1; i <= A; i++)
    	{
    		cin >> f[i];
    	}
    
    	sort(f + 1, f + A + 1);
    	int l = 1, r = f[A] - f[1];
    
    	
    	int mid;
    	while (l <= r)
    	{
    		 mid = (r + l) / 2;
    		//cout << mid << endl;
    		if (check(mid))
    			l = mid + 1;
    		else
    			r = mid - 1;
    	}
    	cout << l-1;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，114人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷P1093--奖学金

P1093 \[NOIP2007 普及组\] 奖学金 -------------------- [原题题意][Link 1] ------------------

妖狐艹你老母/ 2022年10月31日 12:19/ 0 赞/ 275 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 337 阅读

相关洛谷P1540 机器翻译

题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文

怼烎@/ 2022年05月31日 07:41/ 0 赞/ 198 阅读

相关洛谷P1316 丢瓶盖

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

素颜马尾好姑娘i/ 2022年05月29日 08:17/ 0 赞/ 115 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 339 阅读

相关洛谷P1540——机器翻译

题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义

傷城~/ 2022年04月14日 06:55/ 0 赞/ 321 阅读

相关洛谷P1002题解

include<iostream> using namespace std; long long a[30][30]={0},n,m,my,m

我会带着你远行/ 2022年03月19日 04:16/ 0 赞/ 369 阅读

相关洛谷 P1113 杂务

洛谷 P1113 杂务 Description `John`的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起

灰太狼/ 2021年11月10日 02:26/ 0 赞/ 384 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 459 阅读

相关洛谷 P1396 营救

　　　　　　　　　　　　　　　　　　　　[洛谷 P1396 营救][P1396] 题目描述 “咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查

怼烎@/ 2021年10月01日 00:04/ 0 赞/ 464 阅读