欣欣賣場為了讓顧客在購買商品時容易買到所需的商品,因此會把商品分散擺放在賣場的不同區域。當店員發現同種商品在每個區域的數量分配不均,就會將各區域商品的數量重新分配。
舉例來說,如果在 賣場有八個區域,商品擺設以八個字元的字串 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