FZU 2159 WuYou（贪心）
最后更新于：2022-04-01 15:52:55
题目链接：[点击打开链接](http://acm.fzu.edu.cn/problem.php?pid=2159)
该题算是比较简单的贪心了， 只要理顺思路， 不是很复杂的。
我们可以按照这样的规则进行：
从前向后扫一遍， 将？和a[i] == b[i]的情况忽略， 当第一次出现a[i] != b[i]的时候， 分情况讨论如下：
1.如果a[i] < b[i] ， 在这种情况下如果a[i]前面没有？ 那么后面的？无论是多少都能满足条件， 所以将后面的？都变成9就行了。 如果a[i]前面有？ 那么把i前面的？变成b[i]，后面的？变成9（不加证明，用反证法很容易证明）
2.如果a[i] > b[i] ， 如果a[i]前面没有？ 那么显然是输出-1， 如果a[i]前面有？， 那么从i向前扫， 将？变成b[i]-1， 但是要注意当b[i] == 0时是不可以的。 然后如果存在第一个满足条件的k， 让k前面的？和b串相等， 后面的？变成9 。
3.如果所有的a[i] == b[i]， 那么就像a[i] > b[i]那样从最后向前处理就行了。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100000 + 10;
int T,n,m;
char A[maxn], B[maxn];
int main() {
scanf("%d",&T);
while(T--) {
scanf("%s%s",A,B);
int cur = 0, len = strlen(A);
bool ok = false;
for(int i=0;i<len;i++) {
if(A[i] == '?') { cur = 1; continue; }
if(A[i] < B[i]) {
if(cur == 0) {
for(int j=i;j<len;j++) if(A[j] == '?') A[j] = '9';
ok = true; break;
}
else {
for(int j=0;j<i;j++) if(A[j] == '?') A[j] = B[j];
for(int j=i;j<len;j++) if(A[j] == '?') A[j] = '9';
ok = true; break;
}
}
else if(A[i] > B[i]) {
if(cur == 0) {
A[0] = '-'; A[1] = '1'; A[2] = '\0';
ok = true; break;
}
else {
int res = 0;
for(int j=i;j>=0;j--) {
if(A[j] == '?' && ((B[j] > '1') || (B[j] > '0' && j != 0))) {
A[j] = B[j] - 1;
ok = true;
res = 1;
for(int k=0;k<j;k++) if(A[k] == '?') A[k] = B[k];
for(int k=j+1;k<len;k++) if(A[k] == '?') A[k] = '9';
break;
}
}
if(!res) {
A[0] = '-'; A[1] = '1'; A[2] = '\0'; break;
}
else break;
}
}
}
if(!ok) {
for(int i=len-1;i>=0;i--) {
if(A[i] == '?' && (B[i] > '1' || (B[i] > '0' && i != 0))) {
A[i] = B[i] - 1;
ok = true;
for(int k=0;k<i;k++) if(A[k] == '?') A[k] = B[k];
for(int k=i+1;k<len;k++) if(A[k] == '?') A[k] = '9';
}
}
if(!ok) {
A[0] = '-'; A[1] = '1'; A[2] = '\0';
}
}
printf("%s\n",A);
}
return 0;
}
~~~