F. Restore a Number
链接:
http://codeforces.com/contest/670/problem/F
题意:
给你一个数字字符串,再加上长度,然后打乱
再给你一个原字符串的子串,求出最小的原字符串
题解:
其实字符串的长度是确定的,只会有一个解,先算出字符串长度,枚举位数就行了
然后先把还没有用的数字按从小到大的顺序加到ans里,接下来就要把子串加进去,但有几个特殊情况
如果ans为空,那就直接等于子串
如果子串以0开头 那就不能放在开头,肯定要加中间,同时如果ans也以0开头,就需要找一个最小的不为0的和开头交换一下,然后把子串插入进去就行了
如果ans全部为0,或者除了0之外最小的数字比子串开头的数字大,那就只能加到结尾
接下来就是一般的情况了
先记下直接把子串加到ans开头,记为a
然后就是插入子串了,自己想一下 就知道应该差入到哪里了,有两个地方都算一下,再和a比较取最小值就可以了
代码:
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 using namespace std; 5 6 int num[10]; 7 string s1, s2; 8 9 int main() 10 { 11 int E[10] = { 1 }; 12 for (int i = 1; i <= 9; i++) E[i] = E[i - 1] * 10; 13 cin >> s1 >> s2; 14 15 int sum; 16 for (int i = 1; i <= 8; i++) { 17 sum = s1.length() - i; 18 if (sum >= E[i - 1] && sum <= E[i]) break; 19 } 20 for (int i = 0; i < s1.length(); i++) num[s1[i] - '0']++; 21 for (int i = 0; i < s2.length(); i++) num[s2[i] - '0']--; 22 while (sum) { 23 int t = sum % 10; 24 sum /= 10; 25 num[t]--; 26 } 27 28 string ans; 29 for (int i = 0; i < 10; i++) 30 for (int j = 0; j < num[i]; j++) 31 ans += i + '0'; 32 33 int t = -1; 34 for (int i = 0; i < ans.length(); i++) 35 if (ans[i] != '0') { t = i; break; } 36 37 if (ans.length() == 0) ans = s2; 38 else if (s2[0] == '0') { 39 if (ans[0] == '0') swap(ans[0], ans[t]); 40 ans.insert(t + 1, s2); 41 } 42 else if (t == -1 || ans[t] > s2[0]) ans = s2 + ans; 43 else { 44 string a = s2 + ans; 45 if (ans[0] == '0') swap(ans[0], ans[t]); 46 int l, r; 47 l = 1; 48 r = ans.length() - 1; 49 while (ans[l] < s2[0] && l < ans.length()) l++; 50 while (ans[r] > s2[0] && r >= 0) r--; 51 string ansl, ansr; 52 ansl = ansr = ans; 53 ansl.insert(l, s2); 54 ansr.insert(r + 1, s2); 55 ans = min(ansl, ansr); 56 ans = min(ans, a); 57 } 58 cout << ans << endl; 59 return 0; 60 }