資料結構 303 找關聯商品(難)

may

資料結構 303 找關聯商品
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 水果行賣五種水果，分別為「apple」、「watermelon」、「pawpaw」、「banana」和「pineapple」，今天有 N（3 ≤ N ≤ 10）位顧客來買水果。

(2) 請撰寫一程式，讓使用者輸入 N 位顧客買的水果名稱，找出任兩種水果最常被顧客一起購買的前三名組合與購買次數。

提示：五種水果兩兩一組，共有十種組合。

3. 輸入輸出：
輸入說明
第 1 列：正整數 N（3 ≤ N ≤ 10），為顧客人數。
第 2~N+1 列：N 位顧客買水果的資料，資料間以一個半形空白間隔。

輸出說明
請依照購買次數「由多到少」，輸出前三名最常被顧客一起購買的水果組合（任兩種）與購買次數，中間以一個半形空白間隔。

註：
　- 水果組合，請依照水果名稱的字典「由小到大」排序。
　- 若購買次數相同，請依序按照水果名稱的字典「由大到小」排序。

範例輸入1
5
apple watermelon pawpaw
apple pawpaw banana
apple pawpaw pineapple
banana pineapple
watermelon banana pineapple
範例輸出1
apple pawpaw 3
banana pineapple 2
pineapple watermelon 1
範例輸入2
7
apple watermelon pawpaw banana
apple pawpaw banana
apple pawpaw pineapple
banana pineapple
watermelon banana pineapple
apple watermelon pineapple
apple watermelon
範例輸出2
apple watermelon 3
apple pawpaw 3
pineapple watermelon 2

may

回復 3# may
測資:
測資00（基本測資）
5
apple banana
banana pineapple
apple pineapple
apple banana pineapple
pawpaw watermelon
預期輸出（可能順序如下）：

apple banana 2
apple pineapple 2
banana pineapple 2

測資 01（完全不同組合，沒有重複）
3
apple banana
pawpaw pineapple
watermelon banana
預期輸出：
apple banana 1
banana watermelon 1
pawpaw pineapple 1

測資 02（所有人都買相同兩樣）
4
apple banana
apple banana
apple banana
apple banana
預期輸出：
apple banana 4
（其他組合出現次數是 0，不列出）

測資 03（測試字典序處理）
5
watermelon banana apple
pawpaw apple
banana pawpaw
pineapple watermelon banana
apple pineapple pawpaw
預期輸出：
apple pawpaw 2
banana watermelon 2
pawpaw pineapple 1

測資 04
7
apple watermelon pawpaw banana
apple pawpaw banana
apple pawpaw pineapple
banana pineapple
watermelon banana pineapple
apple watermelon pineapple
apple watermelon
範例輸出
apple watermelon 3
apple pawpaw 3
pineapple watermelon 2

may

回復 1# may
題目重點解析
有五種水果：apple、watermelon、pawpaw、banana、pineapple

有 N 位顧客（3 ≤ N ≤ 10），每位顧客都會買幾種水果。

你要統計這些顧客中，每兩種水果一起被買到的次數。

最後輸出購買次數最多的前三組水果組合與對應次數。

同組水果名稱要照字典順序由小到大排列。

若次數相同，要照水果組合的字典序由大到小排（例如：pineapple watermelon > banana pineapple）。

may

回復 1# may

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int n;
   
4. map<string, int> mp;
   
5. vector<pair<string, int>> v;
   
6. string s;
   
7. /*
   
8. n：顧客人數。
   
9. mp：紀錄每個水果組合出現的次數，鍵為「水果1 水果2」的字串。
   
10. v：存放最終要排序用的 pair（水果組合，次數）。
    
11. s：輔助字串，讀入用。*/
    
12. 
    
13. void putIn(vector<string> v)
    
14. {
    
15.     int len=v.size();
    
16.     for(int i=0; i<len-1; i++)
    
17.     {
    
18.         for(int j=i+1; j<len; j++)
    
19.         {
    
20.             string s1=v[i], s2=v[j];
    
21.             if(s1>s2)
    
22.                 swap(s1, s2);
    
23.             mp[s1+" "+s2]++;
    
24.         }
    
25.     }
    
26. }
    
27. /*
    
28. 這段程式的目的是：
    
29. 每位顧客買的水果中，兩兩列出所有可能組合，並按照字典序（小→大）做字串組合作為鍵值，對應的值為出現次數。
    
30. */
    
31. bool compare(pair<string, int> p1, pair<string, int> p2)
    
32. {
    
33.     if(p1.second==p2.second)
    
34.         return p1.first>p2.first;
    
35.     else
    
36.         return p1.second>p2.second;
    
37. }
    
38. /*
    
39. 符合題目排序規則：
    
40. 優先依照購買次數多排在前面。
    
41. 如果次數相同，則依水果組合的字典序由大到小排。
    
42. */
    
43. int main()
    
44. {
    
45.     cin>>n;
    
46.     getline(cin, s);
    
47.     for(int i=0; i<n; i++)
    
48.     {
    
49.         getline(cin, s);
    
50.         stringstream ss;
    
51.         ss<<s;
    
52.         vector<string> v;
    
53.         string str;
    
54.         while(ss>>str)
    
55.             v.push_back(str);
    
56.         putIn(v);
    
57.     }
    
58. /*
    
59. 這段程式碼會
    
60. 將每一行（顧客的水果清單）拆分成字串陣列，
    
61. 然後丟到 putIn 裡處理所有可能的水果組合。
    
62. */
    
63.     for(auto p: mp)
    
64.         v.push_back({p.first, p.second});
    
65. /*
    
66. 將 map 裡的資料轉成 vector<pair<string, int>> 好進行排序。
    
67. */
    
68.     sort(v.begin(), v.end(), compare);
    
69. /*
    
70. 使用自定義的 compare 進行排序。
    
71. */
    
72.     for(int i=0; i<3; i++)
    
73.         cout<<v[i].first<<" "<<v[i].second<<endl;
    
74. 
    
75.     return 0;
    
76. }

複製代碼