ZeroJudge E973: 滿意度調查 (Survey of Satisfaction)

專長統計學的林羊老師最近出了一個題目,要算問卷調查滿意度 0~9 的出現次數,進而探討不同行銷策略的制定方針。

例如:「11221812」 表示滿意度 1 出現 4 次,滿意度 2 出現 3 次,滿意度 8 出現 1 次。

文文小姐看到一整串數字的時候總是會頭痛,因此想要追求文文小姐的宅男工程師決定運用程式設計課所學,幫助她順利算出問卷各滿意度出現的次數,成功約她出去玩!給定一數字,代表問卷各題的調查滿意度,程式應算出各滿意出現的次數,最後依出現次數由大至小排序並輸出滿意度。

範例測資

範例輸入範例輸出
第一行有一個正整數 N (1 <= N <= 263 − 1),代表該問卷各題的滿意度。(若以 long long int 型態變數儲存 N,以 scanf() 讀入時,請以 %lld 作為格式指定字串。)對於每筆測資輸出 K (1 <= K <= 10) 個滿意度值,K 代表 N 中 0 ~ 9 有出現過的滿意度值個數。由左至右的滿意度出現次數由高至低,次數一樣則輸出滿意度值小者。滿意度值彼此間以空白間隔。
24252644265582 4 5 6 8
12345678910111213141 2 3 4 0 5 6 7 8 9

解題思路

使用「EOF」收「字元」的方式收資料,這樣子一次只會收一個字元不需要使用long long int或是string+stringstream來處理資料,當收到字元時使用 Map 將該數字出現的次數 +1。接下來可以使用 while (true) 迴圈來做輸出判定。每次while迴圈中跑一個For迴圈來確認目前 Map 中最大值的數字為多少,並將其輸出且把該數字的MAP值設為0。當所有大於0的MAP值都輸出過之後就將 While 迴圈 break 掉,最後換行即可。

範例程式碼-ZeroJudge E973: 滿意度調查 (Survey of Satisfaction)

#include <iostream>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    map<int, int>MAP;
    char ch;
    while (cin >> ch)
    {
        MAP[int(ch - '0')]++;
    }
    while (true)
    {
        int max = -999;
        int max_num;
        for (int i = 0; i<10; i++)
        {
            if (MAP[i] > max)
            {
                max = MAP[i];
                max_num = i;
            }
        }
        if (max <= 0)
        {
            break;
        }
        else
        {
            cout << max_num << " ";
            MAP[max_num] = 0;
        }
    }
    cout << "\n";
}

//ZeroJudge E973
//Dr. SeanXD

發佈留言