UVa 11541

題目

http://domen111.github.io/UVa-Easy-Viewer/?11541

給一個字串，內容都會是一個字元 $C$ 接著一串數字 $N$ ，表示要輸出 $N$ 個 $C$

例如: A2B3C1 表示 AABBBC

想法

分別用一個變數 $tmp$ 和 $cnt$ 紀錄當前要輸出的字元以及要輸出的次數

每次遇到數字，就把 $cnt*10$ ， 再將 $cnt$ 加上當前數字

這樣才可以進位，也因為如此， $cnt$ 的初始值要設定為 0

Code

#include<iostream>
using namespace std;
int Case=1,t,cnt=0;
string s;
char tmp;
int main(){
	cin>>t;
	while(t--){
		cout<<"Case "<<Case++<<": ";
		cin>>s;
		cnt=0;
		for(int i=0 ; i<=s.size() ; i++){
			if(i!=s.size() && s[i]>='0' && s[i]<='9'){
				cnt*=10;
				cnt+=s[i]-'0';
			}
			else{
				if(cnt==0){
					tmp=s[i];
				}
				else{
					for(int j=0 ; j<cnt ; j++){
						cout<<tmp;
					}
					cnt=0;
					tmp=s[i];
				}
			}
		}
		cout<<"\n";
	}
	return 0;
}

時間複雜度分析

假設每次輸出的字元數量是 $N$，需要輸出的字元有 $M$ 個

那麼每筆測資的時間複雜度為 $O(NM)$

總時間複雜度為 $O(tNM)$