f679. 公會成員

AC (0.5s, 2.2MB)

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
#include<bits/stdc++.h>
#define speedup ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

int main(){
    speedup;
    int n,q,i,x,l,r,mid,find,num[500003];
    cin >> n >> q;

    //input n array
    for(i=0;i<n;i++){cin >> num[i];}

    //input member number and check
    for(i=0;i<q;i++){
        l=0;r=n-1,find=0;
        cin >> x;
        
        while(l<=r){
            mid = (l+r)/2;

            //find right
            if(num[mid] < x){
                l = mid + 1;
            }

            //find left
            else if(num[mid] > x){
                r = mid - 1;
            }

            //find number
            else if(num[mid] == x){
                find=1;break;
            }
        }

        //output
        if(find){cout << "Yes\n";}
        else{cout << "No\n";}
    }
    return 0;
}

d732. 二分搜尋法

用Python和C刻了這題，我的作法完全一模一樣，但執行速度真的差很多。

AC (2.5s, 24.8MB)

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
try:
    while 1:
        n,k = map(int,input().split())
        a = list(map(int,input().split()))
        b = list(map(int,input().split()))
        for i in b:
            l,r,find = 0,n-1,0
            while l<=r:
                mid = (l+r)//2

                # find right
                if a[mid] < i:
                    l = mid+1
                
                # find left
                elif a[mid] > i:
                    r = mid-1

                # find
                elif a[mid] == i:
                    find = 1
                    break
            
            if find == 1:
                print(mid+1)
            else:
                print(0)
except EOFError:
    pass

AC (79ms, 476KB)

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
#include<stdio.h>

int main(){
    int n,k,i,j;
    while(scanf("%d%d",&n,&k) != EOF){
        int a[n],b;
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        for(i=0;i<k;i++){
            int l=0,r=n-1,find=0,mid;
            scanf("%d",&b);
            while(l <= r){
                mid = (l+r)/2;

                //find right
                if(a[mid] < b){
                    l = mid + 1;
                }

                //find left
                else if(a[mid] > b){
                    r = mid - 1;
                }

                //find number
                else if(a[mid] == b){
                    find=1;break;
                }
            }

            //output
            if(find){printf("%d\n",mid+1);}
            else{printf("0\n");}
        }
    }
    return 0;
}

封面圖源：Pixiv