class Solution {
    public:
        // 通过vector穷举了所有的可能性(由于不同的千百十位对应不同的字符,故此穷举最直接)
        vector<pair<int, string>> group = {
            {1000, "M"},
            {900, "CM"},
            {500, "D"},
            {400, "CD"},
            {100, "C"},
            {90, "XC"},
            {50, "L"},
            {40, "XL"},
            {10, "X"},
            {9, "IX"},
            {5, "V"},
            {4, "IV"},
            {1, "I"},
        };//顺序很重要!
        
        string intToRoman(int num) {
            string output_str;
            
            // 遍历这个group
            for(int i=0;i<group.size();i++)//长度固定因此复杂度为O(1)
            {
                // 注意遍历是从大到小减的~
                while(num>=group[i].first)//通过while循环,取完了,i再变
                {
                    output_str+=group[i].second;
                    num=num-group[i].first;
                }
    
                if(num==0)
                    break;
            }
            return output_str;
        }
    };

  class Solution {
    public:
    
        unordered_map<char, int> define_group=//注意是从小到大
        {
            {'I',1},
            {'V',5},
            {'X',10},
            {'L',50},
            {'C',100},
            {'D',500},
            {'M',1000}
        };
    
        int romanToInt(string s) {
    
            int num_value=0;
            for(int i=0;i<s.size();i++)
            {
                // 若字符串的当前位对应的数字小于下一位对应的数字(对应特殊的4,9等等)
                if(define_group[s[i]]<define_group[s[i+1]])
                {
                    //逐个遍历，逐个相加即可~
                    num_value+=define_group[s[i+1]]-define_group[s[i]];
                    i=i+1;//当前位和下一位都算了，可以跳过
                }
                else//反之,则是当前位和下一位相同
                    num_value+=define_group[s[i]];//直接获取值
            }
    
            // num_value=num_value+define_group[s[s.size()-1]];//最后一个加上
            return num_value;
    
        }
    };