题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3925
题目大意：给定一个大数a,和小数b,问a最少加上多少使得a中含有子串b。
解题思路：让b*1,b*10,b*100与a想减，对每次减的结果取最小值。
测试数据:
100
1340 134
123456 234
9 2
9999 111
10 11
4444 1111
9 1
代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
int n,arr[101],a,b,g;
int t = 0,minn,i,j,k;
char s1[101],s2[101];
string str1,str2;
cin>>n;
while(n--){
a = b = 0;
cin>>s1>>s2;
string str1(s1),str2(s2);
int x = str1.size();
int y = str2.size();
if(str1.find(str2) < str1.size()){
cout<<"Case #"<<++t<<": 0"<<endl;
continue;
}
minn = 1000000000;
if(x < y){
a = atoi(s1),b = atoi(s2);
cout<<"Case #"<<++t<<": "<<b-a<<endl;
}
else{
str1 = "00" + str1;
while(str2.size() <= x + 1){
string s = str2;
k = str2.size() - 1,g = x + 2;
int len2 = str2.size();
cout<<"s2 == "<<s<<endl;
for(i = x + 1; i > x + 1 - len2; --i) {
--g;
if(str2[k] - str1[i] < 0 ) {
arr[g] = (str2[k] - '0') + 10 - (str1[i] - '0');
if (k - 1 >= 0) str2[k-1]--;
}
else arr[g] = str2[k] - str1[i];
k--;
if(k == -1) break;
}
while(arr[g] == 0) g++;
if( x - g < 8){
int tminn=0;
for(i = g; i <= x + 1; i++)
tminn = tminn * 10 + arr[i];
if(minn > tminn)
minn = tminn;
}
str2 = s + '0';
}
cout<<"Case #"<<++t<<": "<<minn<<endl;
}
}
}
本文章ZeroClock原创，但可以转载，因为我们是兄弟。