PAT_甲級_1121 Damn Single (25point(s)) (C++)【二分查找】

目錄

​​1，題目描述​​

​​題目大意​​

​​2，思路​​

​​資料結構​​

​​算法​​

​​3，AC代碼​​

​​4，解題過程​​

​​第一搏​​

​​第二搏​​

1，題目描述

Sample Input:

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333      

Sample Output:

5
10000 23333 44444 55555 88888      

題目大意

給出N對夫妻和M個聚會上人的編号，要是M個人中某個人的配偶不在party上，或者就沒有配偶，那麼這個人便是alone的。按增序輸出這些人的編号。

2，思路

資料結構

• int couple[100000]：ID為5位數字，故100000即可。下标與值表示一對夫妻；
• int party[10000]：按ID增序存放party中的人；
• vector<int> ans：存放alone的人，用于輸出；

算法

1. 接受所有夫妻，填充couple數組：



2. 按增序填充party數組：



3. 設計函數，用二分查找的方法判斷一個人是否有配偶以及配偶是否在party中：



4. ans存放所有alone的人，并輸出（注意ans.size()==0的情況）：

3，AC代碼

#include<bits/stdc++.h>
using namespace std;
int couple[100000], party[10000], N, M;//N夫妻數目 M聚會上人數
bool isAlone(int x){
    int target = couple[x];
    if(target == -1)
        return true;
    int left = 0, right = M - 1, mid;
    while(left <= right){
        mid = (left + right) / 2;
        if(party[mid] == target)
            return false;
        else if(party[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return true;
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    scanf("%d", &N);
    int id1, id2;
    fill(couple, couple + 100000, -1);
    for(int i = 0; i < N; i++){
        scanf("%d %d", &id1, &id2);
        couple[id1] = id2;
        couple[id2] = id1;
    }
    scanf("%d", &M);
    for(int i = 0; i < M; i++){
        scanf("%d", &party[i]);
    }
    sort(party, party+M);
    vector<int> ans;
    for(int i = 0; i < M; i++){
        if(isAlone(party[i])){
            ans.push_back(party[i]);
        }
    }
    if(ans.size() == 0){
        printf("0\n");// !!!不是printf("0\n\n");
    }else{
        printf("%d\n%05d", ans.size(), ans[0]);
        for(int i = 1; i < ans.size(); i++)
            printf(" %05d", ans[i]);
    }
    return 0;
}      

4，解題過程

第一搏

二分查找。。。

#include<bits/stdc++.h>
using namespace std;
int couple[100000], party[10000], N, M;//N夫妻數目 M聚會上人數
bool isAlone(int x){
    int target = couple[x];
    if(target == -1)
        return true;
    int left = 0, right = M - 1, mid;
    while(left <= right){
        mid = (left + right) / 2;
        if(party[mid] == target)
            return false;
        else if(party[mid] < target)
            left = mid + 1;    // ！！！
        else
            right = mid - 1;   // ！！！
    }
    return true;
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    scanf("%d", &N);
    int id1, id2;
    fill(couple, couple + 100000, -1);
    for(int i = 0; i < N; i++){
        scanf("%d %d", &id1, &id2);
        couple[id1] = id2;
        couple[id2] = id1;
    }
    scanf("%d", &M);
    for(int i = 0; i < M; i++){
        scanf("%d", &party[i]);
    }
    sort(party, party+M);
    vector<int> ans;
    for(int i = 0; i < M; i++){
        if(isAlone(party[i])){
            ans.push_back(party[i]);
        }
    }
    if(ans.size() == 0){
        printf("0\n\n");
    }else{
        printf("%d\n%05d", ans.size(), ans[0]);
        for(int i = 1; i < ans.size(); i++)
            printf(" %05d", ans[i]);
    }
    return 0;
}      

第二搏