ZeroJudge J538: Market

Xin Xin Market aims to make it easy for customers to find the products they need by distributing them across different areas of the store. When staff notices uneven distribution of the same product in each area, they will reallocate the quantities of products in each area.
For example, if there are eight areas in the market, and the product arrangement is represented by an eight-character string "AbABaabb", where each English letter represents a product, and uppercase and lowercase letters represent the same product. Assume the quantities of products in the eight areas are 48247362. This means that the first area has 4 units of product A/a, the second area has 8 units of product B/b, and so on.

Product A/a is placed in four areas with a total quantity of 4+2+7+3=16 units. After averaging, each area should have 16/4 = 4 units. Product B/b is also placed in four areas with a total quantity of 8+4+6+2=20 units. After averaging, each area should have 20/4 = 5 units. Therefore, the result after reallocation is 45454455.

You need to be aware that if the average quantity of products encounters situations where it cannot be evenly divided, the excess items will be evenly distributed among the areas starting from the back towards the front. For example, the quantity of product aaaaAA, which is 948792, will be redistributed as 666777. This means that the remainder of 39 divided by 6 is 3, and the extra 3 items will be distributed, one each, from the back towards the front of the store areas.
Please design a program to redistribute the quantity of products.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line of input consists of a string S (with a length not exceeding 100), where each character represents a store area.
The types of products in each area are represented by uppercase and lowercase English letters. The same letter in different cases represents the same product.
The second line contains a string T of the same length as S. Each character represents the quantity of the corresponding product in each area.		The output should be a single line representing the redistributed configuration of the store.
AbABaabb
48247362		45454455
KQUrSMRGMkM
37670657138		37660567535
AbCCEabe
26247352		25334365
aaaaAAbbbccC
948792384518		666777555455

Thought Process

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

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

When outputting, just output the last position in the array and then pop_back() the array.

Sample Code－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
Tags

Related Posts

Comments