Proceed big numbers A and B,A and B have same digits(Both A and B have no prelude zeros),A contains uncertain digits marking ‘?’.Find a largest A to make A < B.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int main(){ int caseCnt = 0; cin >> caseCnt; while (caseCnt--) { string a,b; cin >> a >> b; int bound = (int)a.size(); bool flag = false; bool ok = true; for (int i = 0; i < a.size(); i++) { if (a[i] != '?') { if (a[i] > b[i]) { ok = false; bound = i; break; } if (a[i] < b[i]) { bound = i; flag = true; break; } } } if (!ok) { for (int i = bound-1; i >= 0; i--) { if (a[i] == '?') { if (b[i] != '0') { a[i] = b[i] - 1; bound = i; ok = true; flag = true; break; } } } } if (ok) { for (int i = bound-1; i >= 0; i--) { if (a[i] == '?') { if (flag) { a[i] = b[i]; }else if (b[i] != '0') { a[i] = b[i] - 1; bound = i; flag = true; } } } for (int i = bound+1; i < a.size(); i++) { if (a[i] == '?') { a[i] = '9'; } } for (int i = 0; i < a.size(); i++) { if (!isdigit(a[i])) { ok = false; break; } } if (a[0] == '0' && a.size() > 1) { ok = false; } if (a == b) { ok = false; } } if (ok) { cout << a << endl; }else{ cout << -1 << endl; } } return 0; } |
策略是先从前往后扫描一遍已知的数位,如果相等的话,放过当前位,如果当前位a>b这时停止扫描,纪录扫到的位置i,记录状态为1,如果当前位a<b这时停止扫描记录扫描到位置i,状态为2.
对与状态1,如果我们不能在i之前找到一个‘?’使这一位正好比b少1,那么无解,找到了的话,就记录这个新位置为i,跳到状态2。
对于状态2,只要令i左边的数位和B一样,右边的数位都是9就可以了。
都完成之后,做一下最终检查,注意只有一位数时首位可以为0,A!=B就可以了。