吃瓜群众

某地总共有 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 3
1 3 26 7 15
26 99 3
1
2
3
3
0
2

1.参考解答

思路1：暴力查找，每一组群众都对瓜堆进行遍历，时间复杂度为O(n^2)必超时

思路2：

  1. 构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cnt
  2. 进行瓜堆信息的录入
  3. 利用sort函数对node自定义类型按照瓜的数量num进行排序
  4. 二分查找在瓜堆中查找，如果找到输出瓜堆数量num，否则输出0
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
50
51
52
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;


//1.构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cnt
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;
    //2.进行瓜堆信息的录入
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i){
        scanf("%d", &wm[i].cnt);
        wm[i].num = i + 1;
    }
    //3.利用sort函数对node自定义类型按照瓜的数量num进行排序
    sort(wm, wm + n, cmp);
    for(int i = 0; i < m; ++i){
        int temp;
        int l = 0, r = n - 1;
        int flag = 0;
        scanf("%d", &temp);
        //4.利用二分查找在瓜堆中查找，如果找到输出瓜堆数量num，否则输出0
        while(l <= r){
            int mid = (l + r) / 2;
            if(wm[mid].cnt == temp){
                printf("%d\n", wm[mid].num);
                flag = 1;
                break;
            }else if(wm[mid].cnt > temp){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        if(flag == 0){
            printf("0\n");
        }
    }
    
    return 0;
}

2.朴素二分

1
2
3
4
5
6
7
8
9
10
11
while(l <= r){
    int mid = (l + r) / 2;
    if(temp == mid){
        print("%d\n", ans);
        break;
    }else if(mid > temp){
        r = mid - 1;
    }else{
        l = mid + 1;
    }
}