d492: 10226 - Hardwood species

CPE 一顆星選集 49 道必考題

題目連結:https://zerojudge.tw/ShowProblem?problemid=d492

內容

給定若干列字串，計算各字串所占的百分比(取到小數點第四位)，並按照字典序排列。

第一列有一個正整數 n 代表測資數。

範例輸入

2

Red Alder
Ash
Aspen
Basswood
Ash
Beech
Yellow Birch
Ash
Cherry
Cottonwood
Ash
Cypress
Red Elm
Gum
Hackberry
White Oak
Hickory
Pecan
Hard Maple
White Oak
Soft Maple
Red Oak
Red Oak
White Oak
Poplan
Sassafras
Sycamore
Black Walnut
Willow

Red Alder
Ash
Ash
Aspen

範例輸出

Ash 13.7931
Aspen 3.4483
Basswood 3.4483
Beech 3.4483
Black Walnut 3.4483
Cherry 3.4483
Cottonwood 3.4483
Cypress 3.4483
Gum 3.4483
Hackberry 3.4483
Hard Maple 3.4483
Hickory 3.4483
Pecan 3.4483
Poplan 3.4483
Red Alder 3.4483
Red Elm 3.4483
Red Oak 6.8966
Sassafras 3.4483
Soft Maple 3.4483
Sycamore 3.4483
White Oak 10.3448
Willow 3.4483
Yellow Birch 3.4483

Ash 50.0000
Aspen 25.0000
Red Alder 25.0000

想法

使用 getline 一次讀取一列，存入 map 中計算出現次數，運用 map 特性(字串默認排序為字典序)，遍歷一次即可。

因輸入未給字串數量，需額外計算。

參考資料:inversion大神的小屋

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int main(){
    fastio;
    int n, counts;
    string s;
    map <string, int>::iterator iter;
    map <string, int> trees;
    cin >> n >> ws;
    for(int i = 0; i < n; ++i){
        if(i) cout << "\n";
        trees.clear(), counts = 0;
        while(getline(cin, s) && s.size()){
            ++trees[s], ++counts;
        }
        for(iter = trees.begin(); iter != trees.end(); ++iter){
            cout << fixed << setprecision(4) << iter -> first << " " << iter -> second * 100.0 / counts << "\n";
        }
    }
}