▼

20200704 程式實作題 P1. 購物分析 參考解法

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

此題在高中生程式解題系統的題號為：f579. 1. 購物車
題目來源：20200704 APCS 題目整理與詳解

題敘

給定二數字 X,Y，及多個購物清單，問至少買入各一 X,Y 物之訂單有多少筆？買入一物的定義是，該物品加入購物籃的次數大於被拿出購物籃的次數。

購物清單格式：
每筆以 0 結尾，結尾前的各數字若為正整數 k，代表將商品 k 放入購物籃，若為 −k 則代表將 k 拿出。

範例測資

Sample 1

Sample Input 1

1 8
5
1 8 0
5 6 0
2 7 0
8 1 0
33 22 0

Output 1

2

範圍

圖解範例



底下為筆者所想出來的一些解法。

解法一：只用變數
 aCnt：記錄 a 物品放入購物籃的數目
 bCnt：記錄 b 物品放入購物籃的數目
 cnt： 紀錄 T 行中有多少行皆放入 a, b兩物品

C++程式碼：
 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
#include <iostream>

using namespace std;

int main()
{
    int a, b, t;

    // 讀取 a, b, t
    while(cin >> a >> b >> t)
    {
        // aCnt：記錄 a 物品放入購物籃的數目
        // bCnt：記錄 b 物品放入購物籃的數目
        // cnt： 紀錄 T 行中有多少行皆放入 a, b兩物品
        int x, aCnt, bCnt, cnt = 0;

        //  有 T 行資料
        while(t--)
        {
            aCnt = 0, bCnt = 0;

            // 每行資料輸入有多個數 x (以 0 結尾)
            while(cin >> x, x)
            {
                if(x == a) aCnt++;
                if(x == -a) aCnt--;
                if(x == b) bCnt++;
                if(x == -b) bCnt--;
            }

            // 若 a, b 放入購物籃的數目超皆過一個以上
            if(aCnt > 0 && bCnt > 0)
                cnt++;
        }

        cout << cnt << endl;
    }
    return 0;
}

Python 程式碼：
 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
while True:
    try:
        a, b = input().split()
        a = int(a)
        b = int(b)
    
        t = int(input()) # 有 T 行資料
        cnt = 0 # cnt： 紀錄 T 行中有多少行皆放入 a, b兩物品

        while t > 0:
            aCnt = 0 # aCnt：記錄 a 物品放入購物籃的數目
            bCnt = 0 # bCnt：記錄 b 物品放入購物籃的數目
            data = input().split()

            for x in data:
                x = int(x)
                if x == a: aCnt = aCnt + 1
                if x == -a: aCnt = aCnt - 1
                if x == b: bCnt += 1
                if x == -b: bCnt -= 1

            # 若 a, b 放入購物籃的數目超皆過一個以上
            if aCnt > 0 and bCnt > 0:
                cnt += 1
            t = t - 1
        print(cnt)
    except EOFError:
        break


解法二：用陣列
cnt： 紀錄 T 行中有多少行皆放入 a, b兩物品
num[]：紀錄每種物品的購買數目

C++程式碼：
 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
#include <iostream>

using namespace std;

int main()
{
    int a, b, t;

    // 讀取 a, b, t
    while(cin >> a >> b >> t)
    {
        // cnt： 紀錄 T 行中有多少行皆放入 a, b兩物品
        int x, cnt = 0;

        //  有 T 行資料
        while(t--)
        {
            // num[]：紀錄每種物品的購買數目
            int num[101] = {0};


            // 每行資料輸入有多個數 x (以 0 結尾)
            while(cin >> x, x)
            {
                if(x > 0)
                    num[x] += 1;
                if(x < 0)
                    num[-x] -= 1;
            }

            // 若 a, b 放入購物籃的數目超皆過一個以上
            if(num[a] > 0 &&  num[b] > 0)
                cnt++;
        }

        cout << cnt << endl;
    }
    return 0;
}



解法三：用key-value的 map
恩，這個語法和陣列差異不大。
cnt： 紀錄 T 行中有多少行皆放入 a, b兩物品
num：紀錄每種物品的購買數目

C++程式碼：
 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
#include <iostream>
#include <map>

using namespace std;

int main()
{
    int a, b, t;

    // 讀取 a, b, t
    while(cin >> a >> b >> t)
    {
        // cnt： 紀錄 T 行中有多少行皆放入 a, b兩物品
        int x, cnt = 0;

        //  有 T 行資料
        while(t--)
        {
            // num：紀錄每種物品的購買數目
            map<int, int> num ;


            // 每行資料輸入有多個數 x (以 0 結尾)
            while(cin >> x, x)
            {
                if(x > 0)
                    num[x] += 1;
                if(x < 0)
                    num[-x] -= 1;
            }

            // 若 a, b 放入購物籃的數目超皆過一個以上
            if(num[a] > 0 &&  num[b] > 0)
                cnt++;
        }

        cout << cnt << endl;
    }
    return 0;
}


沒有留言:

張貼留言