ZeroJudge J538: 賣場設置 (Market)

欣欣賣場為了讓顧客在購買商品時容易買到所需的商品,因此會把商品分散擺放在賣場的不同區域。當店員發現同種商品在每個區域的數量分配不均,就會將各區域商品的數量重新分配
舉例來說,如果在 賣場有八個區域,商品擺設以八個字元的字串 AbABaabb 來表示,每個英文字母表示一種商品,同字母大小寫均代表同一種商品。假設八個區域的商品數量分別為 48247362,即第一個區域擺放商品 A/a,數量有 4 個,第二個區域擺放商品 B/b,數量有 8 個。

商品 A/a 擺放在四個區域,總數量為 4+2+7+3=16 個,平均後每個區域應擺
放的數量為 16/4 = 4 個。商品 B/b 也擺放在四個區域,總數量為 8+4+6+2=20 個,平均後每個區域應擺放的數量為 20/4 = 5 個。因此重新擺放後的結果為45454455。

要注意的是,若商品數量的平均遇到無法整除的情況,則會將多餘平均的商品由賣場較後面的區域往前平均分攤,舉例:商品 aaaaAA 的數量 948792 會被配置成 666777。即 39 取 6 的餘數為 3,多出的 3 個會由後往前各放一個。
請你設計一個程式重新分配商品數量。

範例測資

範例輸入範例輸出
輸入第一列有一串文字 S (長度不超過 100),每個字元分別表示賣場一個
區域的商品種類,輸入有大寫和小寫英文字母,同一個字母的大小寫表示為同
一種商品。第二列有一串文字 T,與 S 長度相同,每個字元都是一個數字字元,分別表示商品在每個區域的數量。
輸出一行表示重新擺放後的賣場配置。
AbABaabb
48247362
45454455
KQUrSMRGMkM
37670657138
37660567535
AbCCEabe
26247352
25334365
aaaaAAbbbccC
948792384518
666777555455

解題思路

宣告兩個 Map<char, int>,分別存每個字元有多少商品和每個字元有幾件商品,可以使用 toupper 來將所有字元都轉換成大寫的。

再來一個字元一個字元進行判斷,宣告兩個變數,分別為這個字元的商品數量平均值以及餘數。宣告一個 Map<char, vector<int>> 來存答案,跑一個 For迴圈 將目前字元的答案存到剛剛宣告的 Map 中,如果現在的位置+餘數 >= 這個字元的商品數,就將答案++。所有答案都存到陣列之後將陣列倒轉。

輸出時就輸出陣列中的最後一個位置並且 pop_back()。

範例程式碼-ZeroJudge J538: 賣場設置 (Market)

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string store, item;
    cin >> store >> item;
    map<char, int>money, amount;
    for (int i = 0; i<store.length(); i++)
    {
        money[toupper(store[i])] += int(item[i] - '0');
        amount[toupper(store[i])]++;
    }
    map<char, vector<int>>ans;
    for (auto it:money)
    {
        int left = it.second % amount[it.first];
        int calc = it.second / amount[it.first];
        for (int i = 0; i<amount[it.first]; i++)
        {
            int tmp = calc;
            if (i + left >= amount[it.first]) tmp++;
            ans[it.first].push_back(tmp);
        }
        reverse(ans[it.first].begin(), ans[it.first].end());
    }
    for (int i = 0; i<store.length(); i++)
    {
        cout << ans[toupper(store[i])][int(ans[toupper(store[i])].size())-1];
        ans[toupper(store[i])].pop_back();
    }
    cout << "\n";
}

//ZeroJudge J538
//Dr. SeanXD

發佈留言