吃瓜群总升级版
某地总共有 M 堆瓜，第 i 堆瓜的数量为 Xi。
现有 N 组群众现在想要吃瓜，第 i 组群众想要吃的瓜的数量为 Yi。
现在对于每组想吃瓜的群众，需要在 M堆瓜中查找大于等于需要数量的第一堆瓜，并输出那堆瓜的编号，若所有瓜堆的数量均小于需要数量，则输出 0。
输入：
输入共 3 行。
第一行两个整数 M,N。
第二行 M 个整数分别表示 X1,X2……XM。（保证各不相同）
第三行 N 个整数分别表示 Y1,Y2……YN。（保证各不相同）
输出：
对于每个 Yi 输出一行一个整数为大于等于需要数量的第一堆瓜的编号，若所有瓜堆的数量均小于需要数量，则输出 0。
样例：
1
2
3
| 5 5
1 3 26 7 15
27 10 3 4 2
|
1.思路分析
二分查找特殊情况的探讨01：
二分查找特殊情况的探讨10：
2.参考解答
- 构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cnt
- 进行瓜堆信息的录入
- 若所有瓜堆的数量均小于需要数量输出0，否则输出大于等于需要数量的第一堆瓜的编号
- 方法1：建立一个最大虚拟瓜堆并将瓜堆数量置为0，当正常瓜堆中没有瓜堆满足条件时输出虚拟瓜堆数量
- 方法2：用最大的瓜堆的瓜数量判断，如果最大瓜堆数量大于需求则有答案进行二分，否则直接输出0
- 利用sort函数对node自定义类型按照瓜的数量num进行排序
- 利用二分查找在瓜堆中查找，如果找到输出瓜堆数量num
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
| #include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node {
int num, cnt;
};
node wm[100005];
bool cmp(const node &a, const node &b){
return a.cnt < b.cnt;
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i){
scanf("%d", &wm[i].cnt);
wm[i].num = i + 1;
}
wm[n].num = 0, wm[n].cnt = 2100000000;
sort(wm, wm + n, cmp);
for(int i = 0; i < m; ++i){
int temp;
int l = 0, r = n;
scanf("%d", &temp);
while(l != r){
int mid = (l + r) / 2;
if(wm[mid].cnt >= temp){
r = mid;
}else{
l = mid + 1;
}
}
printf("%d\n", wm[l].num);
}
return 0;
}
|
3.总结
总结二分的两种特殊情况
1
2
3
4
5
6
7
8
9
|
while(l != r){
int mid = (l + r) / 2;
if(wm[mid].cnt >= temp){
l = mid;
}else{
l = mid - 1;
}
}
|
1
2
3
4
5
6
7
8
9
|
while(l != r){
int mid = (l + r + l) / 2;
if(wm[mid].cnt >= temp){
r = mid;
}else{
l = mid + 1;
}
}
|
