洛谷二分题解合集

发布时间:2024年01月06日

前言

今天带着大家根据C++:第十讲二分查找-CSDN博客?继续讲一下二分的题目。

P1102 A-B 数对

题目背景

出题是一件痛苦的事情!

相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!

题目描述

给出一串正整数数列以及一个正整数?C,要求计算出所有满足A?B=C?的数对的个数(不同位置的数字一样的数对算不同的数对)。

输入格式

输入共两行。

第一行,两个正整数?N,C。

第二行,N?个正整数,作为要求处理的那串数。

输出格式

一行,表示该串正整数中包含的满足A?B=C?的数对的个数。

输入 #1

4 1
1 1 2 3

输出 #1

3

说明/提示

对于?75%的数据,1≤N≤2000。

对于?100%的数据,1≤N≤2×105,0≤ai?<230,1≤C<230。

解题思路

这一题将A-B=C转换成A-C=B,首先将A数组每个元素出现的次数统计起来,用map映射,最后将A数组每次减一个C,再将A数组扫一遍,将所有映射的次数和加起来就是答案。

看到数据规模后就应该想到是nlogn的算法或者n的,O(n)复杂度的算法可能不太好想,毕竟题中没有给规定数的大小,只是longint,这样如果是桶的思想可能就会爆掉,那么对于A-B=C这个式子来说,两个变量都在等号同侧,这样只能n方枚举,肯定T,那么我们考虑移项,则有A-C=B,这样两边分别都含变量,我们每次枚举A,这样问题就转换为寻找数组中元素为A-C的个数,白皮书上很明确的提到过这一技巧。二分即可。

AC

#include<bits/stdc++.h>
using namespace std; 
using namespace std;
typedef long long LL;
    LL a[200001];
    map<LL,LL> m;
    int main() {
        int n;
        LL c;
        LL ans=0;
        cin >> n >> c;
        for(int i=1;i<=n;i++) {
            cin >> a[i];
            m[a[i]]++;
            a[i]-=c;    
        } 
        for(int i=1;i<=n;i++) ans+=m[a[i]];
        cout << ans << endl;
    return 0;
}

P1571 眼红的Medusa?

题目描述

虽然 Miss Medusa 到了北京,领了科技创新奖,但是她还是觉得不满意。原因是:他发现很多人都和她一样获了科技创新奖,特别是其中的某些人,还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项,Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项,来知道自己有多眼红。

输入格式

第一行两个整数n,m,表示有n?个人获得科技创新奖,m?个人获得特殊贡献奖。

第二行?n?个正整数,表示获得科技创新奖的人的编号。

第三行m?个正整数,表示获得特殊贡献奖的人的编号。

输出格式

输出一行,为获得两个奖项的人的编号,按在科技创新奖获奖名单中的先后次序输出。

输入 #1

4 3
2 15 6 8
8 9 2

输出 #1

2 8

说明/提示

对于?60%的数据,0≤n,m≤1000,获得奖项的人的编号 <2×109;

对于?100%的数据,0≤n,m≤105,获得奖项的人的编号 <2×109。

输入数据保证第二行任意两个数不同,第三行任意两个数不同。

解题思路

我是什么算法?

说白了就是:

暴搜!

但是,纯暴搜是肯定要超时的,所以我们要加一个小小的优化:

规则是这样的:

设a为科技创新奖,b为特殊贡献奖。

如果a[i]>b[j],那么a[i+1]也必定大于b[j](我用的是升序排序),之后同理。

所以,出现这种情况时,j可以毫不犹豫地向后加,一直加到b[j]不小于a[i]为止。

然后判断一不一样就可以了。

这就是一个很简单,却很实用的优化,可以AC。

AC

#include<bits/stdc++.h>
using namespace std;
int n,m;
map<int,bool> v;
int a[101000];
int b[101000];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>b[i];
		v[b[i]]=true;
	}
	for(int i=1;i<=n;i++){
		if(v[a[i]]){
			cout<<a[i]<<" ";
		}
	}
	return 0;
}

P1824 进击的奶牛?

题目描述

Farmer John 建造了一个有 N(2≤N≤105) 个隔间的牛棚,这些隔间分布在一条直线上,坐标是 x1?,x2?,?,xN?(0≤xi?≤109)。

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

输入格式

第?11?行:两个用空格隔开的数字?N?和?C。

第 2~N+1?行:每行一个整数,表示每个隔间的坐标。

输出格式

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

输入 #1

5 3
1
2
8
4
9

输出 #1

3

解题思路

非常经典的一道二分答案模板题
什么是二分答案?简单地说,就是和二分查找相似,二分每个答案,然后对这个答案进行求证,看是否满足条件,然后再次进行左右区间查找,知道二分到单个点上
这一题,我们二分答案找每个牛棚之间的最大距离。

AC

#include<bits/stdc++.h>
using namespace std;
int const N=1e5+5;
int a[N],n,m,l,r,mid;
bool C(int x){
	int sum=1;
	int last=1;
	for(int i=2;i<=n;i++){
		if(a[i]-a[last]>=x){
			sum++;
			last=i;
		}
	}
	return sum>=m;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	l=0,r=1e9+5;
	while(r-l>1){
		mid=(l+r)/2;
		if(C(mid)){
			l=mid;
		}
		else{
			r=mid;
		}
	}
	cout<<l<<endl;
	return 0;
}

P1577 切绳子

题目描述

有?N?条绳子,它们的长度分别为 Li?。如果从它们中切割出?K?条长度相同的绳子,这?K?条绳子每条最长能有多长?答案保留到小数点后?22?位(直接舍掉?22?位后的小数)。

输入格式

第一行两个整数?N?和?K,接下来?N?行,描述了每条绳子的长度 Li??。

输出格式

切割后每条绳子的最大长度。答案与标准答案误差不超过?0.010.01?或者相对误差不超过?1%1%?即可通过。

输入 #1

4 11
8.02
7.43
4.57
5.39

输出 #1

2.00

说明/提示

对于?100%的数据0<Li?≤100000.00,0<n≤10000,0<k≤10000

解题思路

我们直接二分答案,区间的l取0、r取长度和,然后check时对每条长度除以二分的值向下取整,判断是否不小于k就行了。楼下基本是转换成整型进行二分,我这里直接对实型进行二分,然后输出时稍微处理就行了。

二分查找,设C(x)为=可以得到K条长度为x的绳子。

由于长度为L的绳子最多可以切出floor(L/x)段长度为x的绳子,因此C(x)=(floor(L/x)的总和是否大于等于K)由于1次循环可以缩小区间的一半,100次循环可以达到10^-30的精度,是绝对够了的。

AC

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
double a[N],l,r,mid;
int n,k;
int C(double x){
	int ans=0;
	for(int i=1;i<=n;i++){
		ans+=(int)(a[i]/x);
	}
	return ans>=k;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	l=0;r=1e9;
	for(int t=0;t<100;t++){
		mid=(r+l)*0.5;
		if(C(mid)){
			l=mid;
		}
		else{
			r=mid;
		}
	}
	printf("%.2lf",floor(l*100)/100);
	return 0;
}

P2440 木材加工?

题目描述

木材厂有?n?根原木,现在想把这些木头切割成?k?段长度均为?l?的小段木头(木头有可能有剩余)。

当然,我们希望得到的小段木头越长越好,请求出?l?的最大值。

木头长度的单位是?cmcm,原木的长度都是正整数,我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为?11?和?21,要求切割成等长的?6段,很明显能切割出来的小段木头长度最长为?5。

输入格式

第一行是两个正整数n,k,分别表示原木的数量,需要得到的小段的数量。

接下来?n?行,每行一个正整数Li?,表示一根原木的长度。

输出格式

仅一行,即?l?的最大值。

如果连?1cm1cm?长的小段都切不出来,输出?0

输入 #1

3 7
232
124
456

输出 #1

114

说明/提示

数据规模与约定

对于?100%的数据,有 1≤n≤105,1≤k≤108,1≤Li?≤108(i∈[1,n])。

解题思路

二分答案就是说用?二分?的方法枚举答案,具体请看例子:

我现在在一堆木头中找最长的,我可以用一下方法:

  1. 最找到可行范围内最中间的数,用 check函数判断他是否可行,分两种情况:
  • 如果可行(check函数返回1)标记,返回 chazhao(mid,r)
  • 如果不可行(check函数返回0)标记,返回 chazhao(l,mid)

表如下:

12345678910
1111100000

AC

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[100007]; 
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int l=0,r=1e8+1,m;
	while(l+1<r){
		m=(l+r)/2;
		int cnt=0;
		for(int i=1;i<=n;i++)
		cnt+=a[i]/m;
		if(cnt>=k){
			l=m;
		}
		else{
			r=m;
		}
	}
	cout<<l<<endl;
	return 0;
}

附加难题——P1281 书的复制

链接——书的复制 - 洛谷

解题思路

而言之,就是:

把m个数分成k组,使每组数的和尽量平均。

那么,我们需要二分的其实是这个“平均”的值,也就是复制时间。

把二分出来的复制时间代到输入数据中,就可以判断这个复制时间是否可行。根据题目要求:

尽可能让前面的人少抄写

emmm这个怎么实现呢?

其实啊,我们这么想:我们面前有一面长长的桌子,桌子上从左到右整整齐齐摆着m本书,有k个可怜的娃要去抄书。要使前面的人少抄写,也就是抄靠右边的书的娃要多抄。那么,就要从抄靠右边的书的娃开始枚举,让他尽量多抄。

AC

#include<bits/stdc++.h>
const int N=505;
using namespace std;
int m,k,p[N],f[N][N],sum[N],maxmin;
void Print(int x)
{
	if(!x)	return;
	for(int i=x;i>=0;i--)
	{
		if(sum[x]-sum[i-1]>maxmin||i==0)
		{
			Print(i);
			cout<<i+1<<" "<<x<<endl;
			break;
		}
	}
}
int main()
{
	cin>>m>>k;	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=m;i++)	
	{
		cin>>p[i];
		sum[i]=sum[i-1]+p[i];
		f[i][1]=sum[i];
	}
	f[1][0]=0;
	for(int i=2;i<=k;i++)
		for(int j=1;j<=m;j++)
			for(int q=1;q<j;q++)
				f[j][i]=min(f[j][i],max(f[q][i-1],sum[j]-sum[q]));
	maxmin=f[m][k];
	Print(m);
	return 0;
}

结尾

如果有人想在洛谷上做题,可以点下方链接:

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

如果你喜欢或想了解一下其他的算法,可以看看以下这些:

DFS深搜:

C++:第十二讲DFS深搜(二)-CSDN博客

C++:第十一讲DFS深搜-CSDN博客

最后认识一下,我是爱编程的喷火龙廖,我们有缘再见!

文章来源:https://blog.csdn.net/2301_81328824/article/details/135423221
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。