对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211。注意打乱后原来的正整数可能被拆开，比如在90811211中，原来的正整数10就被拆成了0和1。
现给定一个按如上规则得到的打乱了字符的字符串，请将其还原成连续正整数序列，并输出序列中最小的数字。
输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，字符串长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列.
输出一个数字，为序列中最小的数字
19801211 5
8
还原出的序列为8 9 10 11 12，故输出8
432111111111 4
111
还原出的序列为111 112 113 114，故输出111
首先，对题目进行解析，我们知道原始序列一定是一个连续的正整数序列，也就是说，序列中的元素是等差递增的，差为1。另外，由于原始序列是由数字组合而成的字符串，所以原始序列和打乱后的字符串的ASCII码之和是一致的。
于是，我们可以使用以下的步骤来解决这个问题：
在复杂度分析方面，我们需要对输入的字符串进行排序，这个操作的时间复杂度是O(n log n)，其中n是字符串的长度。接下来，我们需要枚举最小的数字，由于数字的范围是有限的，所以这个操作的时间复杂度是O(1)。然后，对于每一种可能的数字，我们需要生成一个序列，并计算这个序列的ASCII码之和，这个操作的时间复杂度是O(m)，其中m是序列的长度。所以，总的时间复杂度是O(n log n + m)，空间复杂度是O(n)。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void* a, const void* b) {
return *(char*)a - *(char*)b;
}
int asciiSum(char* s) {
int sum = 0;
for (int i = 0; s[i] != '\0'; i++) {
sum += s[i] - '0';
}
return sum;
}
char* generateSequence(int startNum, int len) {
char* sequence = malloc(201 * sizeof(char));
char buffer[5];
for (int i = 0; i < len; i++) {
sprintf(buffer, "%d", startNum + i);
strcat(sequence, buffer);
}
return sequence;
}
int main() {
char input[201];
int len;
scanf("%s %d", input, &len);
int n = strlen(input);
qsort(input, n, sizeof(char), compare);
int totalSum = asciiSum(input);
int minNumLen = n / len;
char candidate[201] = {0};
int minNum = -1;
for (int i = 0; i <= 9; i++) {
sprintf(candidate, "%d", i);
strncat(candidate, input, minNumLen - 1);
int num = atoi(candidate);
char* sequence = generateSequence(num, len);
if (asciiSum(sequence) == totalSum) {
minNum = num;
free(sequence);
break;
}
free(sequence);
}
printf("%d\n", minNum);
return 0;
}
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int asciiSum(const string& s) {
int sum = 0;
for (char c : s) {
sum += c - '0';
}
return sum;
}
string generateSequence(int startNum, int len) {
string sequence;
for (int i = 0; i < len; i++) {
sequence += to_string(startNum + i);
}
return sequence;
}
int main() {
string input;
int len;
cin >> input >> len;
sort(input.begin(), input.end());
int totalSum = asciiSum(input);
int minNumLen = input.length() / len;
int minNum = -1;
for (int i = 0; i <= 9; i++) {
string candidate = to_string(i) + input.substr(0, minNumLen - 1);
int num = stoi(candidate);
if (asciiSum(generateSequence(num, len)) == totalSum) {
minNum = num;
break;
}
}
cout << minNum << endl;
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int len = sc.nextInt();
int minStartNum = findMinStartNum(s, len);
System.out.println(minStartNum);
}
private static int findMinStartNum(String s, int len) {
int n = s.length();
char[] arr = s.toCharArray();
Arrays.sort(arr);
String sortedStr = new String(arr);
int totalSum = totalAsciiSum(s);
int minNumLen = n / len;
int minNum = -1;
for (int i = 0; i <= 9; i++) {
String candidate = i + sortedStr.substring(0, minNumLen - 1);
int num = Integer.parseInt(candidate);
if (totalAsciiSum(generateSequence(num, len)) == totalSum) {
minNum = num;
break;
}
}
return minNum;
}
private static String generateSequence(int startNum, int len) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
sb.append(startNum + i);
}
return sb.toString();
}
private static int totalAsciiSum(String s) {
int sum = 0;
for (char c : s.toCharArray()) {
sum += c - '0';
}
return sum;
}
}
def min_start_num(s, len):
s = sorted(s)
total_sum = sum(int(i) for i in s)
min_num_len = len(s) // len
min_num = float('inf')
for i in range(10):
candidate = str(i) + ''.join(s[:min_num_len - 1])
num = int(candidate)
if sum(int(i) for i in str(num + i) for i in range(len)) == total_sum:
min_num = min(min_num, num)
return min_num
s, len = input().split()
len = int(len)
print(min_start_num(s, len))
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
readline.question('', input => {
const [s, len] = input.split(' ');
const minStartNum = findMinStartNum(s, parseInt(len));
console.log(minStartNum);
readline.close();
});
function findMinStartNum(s, len) {
const arr = Array.from(s);
arr.sort();
const totalSum = arr.reduce((sum, c) => sum + c.charCodeAt(0) - '0'.charCodeAt(0), 0);
const minNumLen = Math.floor(s.length / len);
let minNum = Infinity;
for (let i = 0; i <= 9; i++) {
const candidate = i.toString() + arr.join('').substring(0, minNumLen - 1);
const num = parseInt(candidate);
if (asciiSum(generateSequence(num, len)) === totalSum) {
minNum = num;
break;
}
}
return minNum;
}
function generateSequence(startNum, len) {
let sequence = '';
for (let i = 0; i < len; i++) {
sequence += (startNum + i).toString();
}
return sequence;
}
function asciiSum(s) {
return Array.from(s).reduce((sum, c) => sum + c.charCodeAt(0) - '0'.charCodeAt(0), 0);
}
package main
import (
"fmt"
"sort"
"strconv"
)
func generateSequence(startNum, length int) string {
result := ""
for i := 0; i < length; i++ {
result += strconv.Itoa(startNum + i)
}
return result
}
func asciiSum(s string) int {
sum := 0
for _, c := range s {
sum += int(c - '0')
}
return sum
}
func findMinStartNum(s string, length int) int {
characters := []byte(s)
sort.Slice(characters, func(i, j int) bool { return characters[i] < characters[j] })
totalSum := asciiSum(s)
minNumLen := len(s) / length
minNum := int(^uint(0) >> 1) // maximum int value
for i := 0; i <= 9; i++ {
candidate := strconv.Itoa(i) + string(characters[:minNumLen-1])
num, _ := strconv.Atoi(candidate)
if asciiSum(generateSequence(num, length)) == totalSum {
minNum = num
break
}
}
return minNum
}
func main() {
var s string
var len int
fmt.Scan(&s, &len)
minStartNum := findMinStartNum(s, len)
fmt.Println(minStartNum)
}