UVA11678 - Cards' Exchange

UVA11678 - Cards' Exchange

四月 05, 2019

題目簡述

題目大概的意思就是說，有兩個人要交換卡片，他們對卡片有些要求

  1. 他們不想要拿到自己拿出去的卡片
  2. 只要有能交換的卡片他們都會拿出來交換
  3. 同一個人不會拿出兩張一樣的卡片做交換

要求符合敘述的最小交換次數

初步想法

將兩個人的卡片集合做 unique 之後去掉交集(共同持有的)，再統計兩個集合剩下的個數，取最小的那個就是答案。
時間複雜度是: O(n^2)

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
53
54
55
56
57
58
59
60
61
/* UVA 11678 - Cards' Exchange
 * Author: ifTNT
 * Total time complexity: O(n^2)
 * Space used: 20000
 */
#include <iostream>
using namespace std;

int main(){
    int m, n;
    int alice[10000];
    int betty[10000];
    cin >> m >> n;
    while(m!=0 || n!=0){
        if(cin.eof()) break;
        for(int i=0; i<m; i++){
            cin >> alice[i];
        }
        for(int i=0; i<n; i++){
            cin >> betty[i];
        }

        //Remove duplicate element. O(n^2)
        for(int i=0; i<m; i++){
            for(int j=i+1; j<m; j++){
                if(alice[j]==alice[i]) alice[j] = -1;
            }
            bool flag = false;
            for(int j=0; j<n; j++){
                if(betty[j]==alice[i]){
                    betty[j] = -1;
                    flag = true;
                }
            }
            if(flag) alice[i] = -1;
        }
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                if(betty[j]==betty[i]) betty[j] = -1;
            }
        }

        //Statistic universal unique element O(n)
        int aliceUniqueCnt=0, bettyUniqueCnt=0;
        for(int i=0; i<m; i++){
            if(alice[i]!=-1){
                aliceUniqueCnt++;
            }
        }
        for(int i=0; i<n; i++){
            if(betty[i]!=-1){
                bettyUniqueCnt++;
            }
        }

        //Take the small one
        cout << (aliceUniqueCnt<=bettyUniqueCnt ? aliceUniqueCnt : bettyUniqueCnt) << endl;

        cin >> m >> n;
    }
}

還能再更快嗎

如果將問題主體改成一張卡片被誰擁有，則可以用 O(n) 的複雜度解決這個問題。但是使用空間會稍微大一點，可以再進一步使用 bitset 之類的資料結構壓縮空間。如果是用 set 來存卡片集合的話因爲 set.count() 的複雜度是 O(lg(n))，因此複雜度會成長爲 O(n*lg(n))

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
53
54
/* UVA 11678 - Cards' Exchange
 * Author: ifTNT
 * Total time complexity: O(n)
 * Space used: 100000
 */
#include <iostream>
using namespace std;

int main(){
    const char alice=0, betty=1, common=2;
    int m, n;
    char card[100000];
    cin >> m >> n;
    while(m!=0 || n!=0){
        if(cin.eof()) break;
        for(int i=0; i<100000; i++){
            card[i]=-1;
        }

        // Read input and regist the card. O(n)
        int buf;
        int maxCard = 0;
        for(int i=0; i<m; i++){
            cin >> buf;
            card[buf] = alice;
            if(buf>maxCard) maxCard = buf;
        }
        for(int i=0; i<n; i++){
            cin >> buf;
            if(card[buf]==alice){
                card[buf] = common;
            }else if(card[buf]!=common){
                card[buf] = betty;
            }
            if(buf>maxCard) maxCard = buf;
        }

        // Statistic universal unique card. O(n)
        int aliceUniqueCnt=0, bettyUniqueCnt=0;

        for(int i=0; i<=maxCard; i++){
            if(card[i]==alice){
                aliceUniqueCnt++;
            }else if(card[i]==betty){
                bettyUniqueCnt++;
            }
        }

        //Take the small one
        cout << (aliceUniqueCnt<=bettyUniqueCnt ? aliceUniqueCnt : bettyUniqueCnt) << endl;

        cin >> m >> n;
    }
}