蓝桥杯 C*++ Calculations 贪心

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 string app = "a++";
 5 string ppa = "++a"; //用于字符串比较 
 6 int nums[10010][2];
 7 // nums[i][0] 存储第i个a++/++a的系数
 8 // nums[i][0] 存储第i个是a++还是++a
 9 // nums[i][1]=0表示是a++，nums[i][1]=1表示是++a
10 int str_int(string s) { // 将一个逆序的字符串转数字,因为遇到 a++/++a 之后往前读，所以顺序反的 
11     int sum = 0;
12     for (int i = s.length() - 1; i >= 0; i--) {
13         sum *= 10;
14         sum += s[i] - ‘0‘;
15     }
16     return sum;
17 }
18 int main() {
19     int a;
20     string s;
21     cin >> a >> s;
22     int len = s.length();
23     int cnt = 0; //cnt存储有多少个a++，++a 
24     // 处理字符串的思路：
25     // 先扫描 a++ 或 ++a，再往前读，获得他们的系数
26     for (int i = 0; i < len - 2; i++) {
27         if (s.substr(i, 3).compare(app) == 0 || s.substr(i, 3).compare(ppa) == 0) { //如果找到了a++或++a 
28             // 判断是a++还是++a
29             int flag; //flag=0表示a++，flag=1表示++a 
30             if (s.substr(i, 3).compare(app) == 0) {
31                 flag = 0; 
32             } else {
33                 flag = 1;
34             }
35             // 第一个位置没有系数，系数直接为1
36             if (i == 0) {
37                 nums[cnt][1] = flag;
38                 nums[cnt++][0] = 1;
39             } else if (s[i - 1] == ‘+‘) { // 如果是加减号，系数也为1 
40                 nums[cnt][1] = flag;
41                 nums[cnt++][0] = 1;
42             } else if (s[i - 1] == ‘-‘) {
43                 nums[cnt][1] = flag;
44                 nums[cnt++][0] = -1;
45             } else if(s[i - 1] == ‘*‘) { // 如果是乘号，直接向前找系数
46                 int idx = i - 2;
47                 string str = "";
48                 while (idx >= 0 && ‘0‘ <= s[idx] && s[idx] <= ‘9‘) {
49                     str += s[idx];
50                     idx -= 1;
51                 }
52                 int sum = str_int(str);
53                 if (idx >= 0 && s[idx] == ‘-‘) {
54                     sum *= -1;
55                 }
56                 nums[cnt][1] = flag;
57                 nums[cnt++][0] = sum;
58             }
59             // 这里直接向后跳三格，防止如下情况
60             // a+++a++，应该是a++ + a++ 的，却变成 a++ ++a a++
61             i += 2;
62         }
63     }
64     // 对系数进行冒泡排序
65     for (int i = 0; i < cnt; i++) { //虽然nums是二位数组，但我们只对其中的系数排序 
66         for (int j = 0; j < cnt - 1; j++) {    
67             if (nums[j][0] > nums[j + 1][0]) {
68                 swap(nums[j][0], nums[j + 1][0]); //注意系数和系数的类型是一体的，要一起变 
69                 swap(nums[j][1], nums[j + 1][1]);
70             }
71         }
72     }
73     // long long 防止溢出
74     ll ans = 0;
75     for (int i = 0; i < cnt; i++) {
76         ans += nums[i][0] * (a + nums[i][1]);
77         a += 1;
78     }
79     cout << ans << endl;
80     return 0;
81 }