首页 > ACM题库 > HDU-杭电 > HDU 3522-Minimum Integer sequence [解题报告]HOJ
2014
11-05

HDU 3522-Minimum Integer sequence [解题报告]HOJ

Minimum Integer sequence

问题描述 :

Now we have two integers A and B, after insert B into A, we can get a new integer C, and then the problem comes: how to get a smallest C? For example, let A = 345, B = 478. As there are there digits in A, so there are four places for B to insert into. We can get 478345, 347845, 344785, 345478.After comparing, we could know that the smallest C is 344785.

输入:

There are multiple test cases. Each test case takes one line, Each line contents two integers A and B(there will be less than 100000 digits in A and B and there is no digit values 0 in A and B), the two integers are separated by a space, process to the end of file.

输出:

There are multiple test cases. Each test case takes one line, Each line contents two integers A and B(there will be less than 100000 digits in A and B and there is no digit values 0 in A and B), the two integers are separated by a space, process to the end of file.

样例输入:

345 478
12345 678
123 123

样例输出:

344785
12345678
112323

#include <cstdio>
#include <cstring>

void exkmp(char s1[],char s2[],int next[],int ex[]) {
	int i,j,p;
	for (i=0,j=0,p=-1;s1[i]!='\0';i++,j++,p--) {
		if (p==-1) {
			j=0;
			do p++; while (s1[i+p]!='\0'&&s1[i+p]==s2[j+p]);
			ex[i]=p;
		} else if (next[j]<p) ex[i]=next[j];
		else if (next[j]>p) ex[i]=p;
		else {
			j=0;
			while (s1[i+p]!='\0'&&s1[i+p]==s2[j+p]) p++;
			ex[i]=p;
		}
	}
	ex[i]=0;
}

char s1[100100];
char s2[100100];
int ex[100100];
int next[100100];
int ls1,ls2;

bool smallerThan(int i,int j) {
	if (ex[j]<i-j) return s1[j+ex[j]]<s2[ex[j]];
	if (next[i-j]<ls2-(i-j)) return s2[next[i-j]]<s2[i-j+next[i-j]];
	if (next[ls2-(i-j)]<(i-j)) return s2[ls2-(i-j)+next[ls2-(i-j)]]<s2[next[ls2-(i-j)]];
	return false;
}

int main() {
	int ans,i;
	while (scanf("%s%s",s1,s2)!=EOF) {
		exkmp(s2+1,s2,next,next+1);
		exkmp(s1,s2,next,ex);
		ls1=strlen(s1);
		ls2=strlen(s2);
		ans=0;
		for (i=0;i<ls1;i++) {
			if (smallerThan(i+1,ans)) ans=i+1;
		}
		for (i=0;i<ans;i++) printf("%c",s1[i]);
		printf("%s",s2);
		for (i=ans;i<ls1;i++) printf("%c",s1[i]);
		printf("\n");
	}
	return 0;
}

  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮