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
Declare two Map variables to store the count of each character representing the number of goods and the count of each character representing the number of goods. You can use toupper to convert all characters to uppercase.
Next, iterate through each character one by one. Declare two variables for each character: the average quantity of goods and the remainder. Declare a Map<char, vector> to store the answers. Run a for loop to store the answer of the current character in the map declared earlier. If the current position + remainder >= the quantity of goods for this character, increment the answer. After storing all answers in the array, reverse the array.
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