专题二 二分法
102400226 石华波 Vjudge账号:DustLi
问题一 二分查找
问题陈述
输入一个整数 n和 n个整数，保证这 n个整数已经按照从小到大进行排序。
然后输入一个整数 q（ q≤100000 ）代表 q次查询。接下来 q行，每行含有一个整数 m，代表一次查询。对于每次查询，使用二分查找判断 m是否在之前输入的 n个整数中出现过。如果出现，输出一行 “Yes”，否则输出 “No 。
解题思路
基本的二分查找，直接套板即可。
AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int array[n];
for(int i=0;i<n;i++) {
cin>>array[i];
}
int q;
cin>>q;
while(q--) {
int m;
cin>>m;
int beg=0,end=n-1,mid=0;
while(beg<=end) {
mid=(beg+end)/2;
if(array[mid]==m) break;
if(array[mid]<m) beg=mid+1;
else end=mid-1;
}
if(array[mid]==m) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
|
问题二 A-B数对
问题陈述
给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C的数对的个数（不同位置的数字一样的数对算不同的数对）。
解题思路
解题时并未联系到二分查找，而是使用Hash表，遍历数组，当HASH表中存在A=B+C时，答案加上A出现的次数。
AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<iostream>
#include<unordered_map>
using namespace std;
int main(){
int N,C;
int tag;
long long ans=0;
cin>>N>>C;
int nums[N];
unordered_map<int,int> numcnt;
for(int i=0;i<N;i++) {
cin>>nums[i];
numcnt[nums[i]]++;
}
for(int i=0;i<N;i++) {
tag=nums[i]+C;
ans+=numcnt[tag];
}
cout<<ans<<endl;
return 0;
}
|
问题三 分巧克力
问题陈述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NN 块巧克力，其中第 i 块是 Hi×Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
- 形状是正方形，边长是整数。
- 大小相同。
例如一块 6×5的巧克力可以切出 6 块 2×2的巧克力或者 2块 3×3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
解题思路
题目要求每块巧克力大小相同，而对于一块H[i]*W[i]的巧克力，最多能切出边长为i的巧克力(H[i]/i)*(W[i]/i)份。
使用二分法，由题意可知最大边长不会超过已知Hi、Wi最大值中较小的那个，故以该值为上界，1为下界，当可切出的块数大于等于K时更新下界，否则更新上界。
AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<iostream>
#include<climits>
using namespace std;
int main(){
int N,K;
cin>>N>>K;
int H[N],W[N];
int Max=INT_MIN;
for(int i=0;i<N;i++) {
cin>>H[i]>>W[i];
Max=max(Max,min(H[i],W[i]));
}
int Min=1;
int mid;
int cnt;
while(Min<Max) {
mid=(Min+Max+1)/2;
cnt=0;
for(int i=0;i<N;i++) {
cnt+=(H[i]/mid)*(W[i]/mid);
}
if(cnt>=K) Min=mid;
else Max=mid-1;
}
cout<<Min<<endl;
return 0;
}
|
问题4 卡牌
问题陈述
这天，小明在整理他的卡牌。
他一共有 n 种卡牌，第 ii 种卡牌上印有正整数数 i(i∈[1,n]), 且第 i种卡牌现有 ai张。
而如果有 n 张卡牌，其中每种卡牌各一张，那么这 n 张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌，拿出了 m 张空白牌, 他可以在上面写上数 i，将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观，决定第 i种牌最多手写 bi张。
请问小明最多能凑出多少套牌?
解题思路
首先，十年OI一场空，不开LongLong见祖宗！
同样是用二分法查找最多能凑出的牌数，此处上界可以是max(Right,b[i]+a[i])，但对结果影响不大，故没有进行修改，使用了与上一题不同的二分板子。
以1为下界，一个足够大的数1e7为上界，Check函数用于检查是否能够凑出mid套牌，如果mid-a[i]>b[i]，说明无论如何此种牌都无法凑到mid张，可直接return 0,循环结束后将sum与m比较，如若sum小于等于m则说明可以凑出mid套牌，反之不然。
AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include<iostream>
#include<climits>
#define ll long long
using namespace std;
const ll N=2e5+10;
ll n,m;
ll a[N],b[N];
ll Check(ll x);
int main() {
cin>>n>>m;
for(ll i=0;i<n;i++) cin>>a[i];
for(ll i=0;i<n;i++) cin>>b[i];
ll Left=0,Right=1e7;
while(Left<Right) {
ll mid=(Right+Left+1)/2;
if(Check(mid)) Left=mid;
else Right=mid-1;
}
cout<<Right<<endl;
return 0;
}
ll Check(ll x) {
ll sum=0;
for(ll i=0;i<n;i++) {
if(x-a[i]>b[i]) return 0;
sum+=x-a[i]>0?x-a[i]:0;
}
return sum<=m;
}
|
问题五 书的复制
问题陈述
现在要把 m 本有顺序的书分给 k个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。
解题思路
二分法此处不表，与上文类似。
复制时间即抄写页数最多的人所抄页数，该值最大为所有书页码之和，最小为页码数最多那本书的页码数，以此为上下界。
Check函数中，检查抄的页数加上当前书的页数是否超过mid（所求复制时间），是则换人，否则继续，最后比较所需人数与实际人数，若所需人数小于等于实际人数则可行，反之不然。
在输出答案时，选择从后往前遍历，即让后面的人多抄以达到前面的人少抄的效果，记录下每个人的结束书号，第一个人的起始书号为1，最后一个人的结束书号为n，当前人的起始书号为上一个人的结束书号+1。
AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<iostream>
#include<climits>
#define ll long long
using namespace std;
int Check(int upp);
int book,people;
int books[502];
int main() {
cin>>book>>people;
int left=0,right=0;
for(int i=1;i<=book;i++) {
cin>>books[i];
right+=books[i];
left=max(left,books[i]);
}
int mid=0;
while(left+1<right) {
mid=(left+right)/2;
if(Check(mid)) right=mid;
else left=mid;
}
int last[505],cnt=1;
last[1]=book+1;
last[people+1]=1;
int pages=0;
for(int i=book;i>0;i--) {
if(pages+books[i]>right) {
pages=0;
last[++cnt]=i+1;
}
pages+=books[i];
}
for(int i=people;i>0;i--) {
cout<<last[i+1]<<" "<<last[i]-1<<endl;
}
return 0;
}
int Check(int upp) {
int pcnt=1,pages=0;
for(int i=book;i>0;i--) {
if(pages+books[i]>upp) pages=0,pcnt++;
pages+=books[i];
}
return pcnt<=people;
}
|
问题六 青蛙过河
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0是允许的)。
小青蛙一共需要去学校上 x天课，所以它需要往返 2x次。当小青蛙具有一个跳跃能力 y时，它能跳不超过 y的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x次课。
解题思路
一只青蛙往返2x次<=>一只青蛙单向过河2x次<=>2x只青蛙单向过河1次。
在第i次跳越中，这些青蛙必将落在[i,y+i-1]的区间中，故每个这样的区间中石头高度之和必须大于等于2x，此为必要性。
接下来说明充分性：当青蛙们在[i,y+i-1]的区间内上落脚时，令落在石头i上的青蛙向前跳跃[1,y]格，则此时所有的青蛙都处于[i+1,y+1]区间中，由于每个区间的石头高度之和均大于等于2x，所以青蛙均能顺利落脚。显然，这2x只青蛙可以在[1,y]上落脚，那么以此类推，他们就可以在[2,y+1]、[3,y+2]……上落脚，故所有青蛙均能过河。
但如果每次都以H[i]+…+H[y+i-1]的方式计算区间高度和，用时就太久了，故计算从石头1到石头n的高度和Sum[i]，每次只需令区间端点的高度和相减即可。
AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include<iostream>
#include<climits>
#define ll long long
using namespace std;
ll Check(ll y);
const ll N=1e5+1;
ll width,days;
ll H[N],Sum[N]={0};
int main() {
cin>>width>>days;
days*=2;
for(ll i=1;i<width;i++) {
cin>>H[i];
Sum[i]=Sum[i-1]+H[i];
}
ll left=1,right=width;
while(left<right) {
ll mid=(left+right)/2;
if(Check(mid)) right=mid;
else left=mid+1;
}
cout<<left<<endl;
return 0;
}
ll Check(ll y) {
for(ll i=y;i<width;i++) {
if(Sum[i]-Sum[i-y]<days) return 0;
}
return 1;
}
|
学习总结
本专题内容主要为二分法的应用，通过学习，解决了两道绿题，提高了自己的能力。