j538 - 賣場設置 (Market)

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個字串 s 和一個字串 n，其中 s 代表賣場的商品名稱，n 代表對應商品的數量。s 中可能包含大小寫字母，代表同一個商品的兩種寫法。要求根據 s 中相同商品的總數量，更新 n 中對應位置的數字，並輸出更新後的 n。

解題思路

這題的核心思想是統計每個商品（不區分大小寫）的總數量，然後將數量分配到 n 字串中對應商品的位置。

1. 統計商品數量： 使用一個大小為 26 的陣列 v 儲存每個字母（不區分大小寫）對應的總數量。使用一個大小為 26 的 vector 陣列 e 儲存每個字母在 s 中出現的位置索引。
2. 遍歷 s： 遍歷字串 s，對於每個字符，判斷其是否為字母。如果是字母，則將其轉換為小寫字母的索引，並將對應的 n 字串的數字轉換為整數後加到 v 陣列中，同時將索引存入 e 陣列。
3. 分配數量： 遍歷 v 陣列，對於每個字母，計算 v 陣列中該字母的總數量除以 e 陣列中該字母出現次數的餘數 mod。
4. 更新 n： 從 e 陣列中該字母出現位置的最後一個開始，依次將 n 字串中對應位置的數字更新為 v 陣列中該字母的總數量除以 e 陣列中該字母出現次數的商加 1，如果 mod 不為 0，則將 n 字串中對應位置的數字更新為 v 陣列中該字母的總數量除以 e 陣列中該字母出現次數的商。

複雜度分析

• 時間複雜度: O(N)，其中 N 是字串 s 的長度。遍歷字串 s 需要 O(N) 的時間，遍歷 v 陣列需要 O(26) 的時間，整體時間複雜度為 O(N)。
• 空間複雜度: O(26)，主要用於儲存 v 和 e 陣列，空間複雜度為 O(1)。

程式碼

#include <iostream>
#include <vector>
using namespace std;
int v[26],mod[26];
string s,n;
vector <int> e[26];
int main(){
	cin >> s >> n;
	for(int i=0;i<s.size();++i){
		if(s[i]>='a'){
			e[s[i]-'a'].push_back(i);
			v[s[i]-'a']+=n[i]-'0';
		}
		else{
			e[s[i]-'A'].push_back(i);
			v[s[i]-'A']+=n[i]-'0';
		}
	}
	for(int i=0;i<26;++i){
		int es=e[i].size();
		if(es==0)continue;
		mod[i]=v[i]%es;//7%4 = 3 = 1 2 2 2
		for(int j=es-1;j>=0;--j){
			if(mod[i]){
				n[e[i][j]]=v[i]/es+1+'0';
				--mod[i];
			}
			else{
				n[e[i][j]]=v[i]/es+'0';
			}
		}
	}
	cout << n;
}