刷題 UVa 10905 Children's Game 解答

Algorithm:

題目是會給好幾個數字，然後要想辦法把這幾個數字拼成一個值最大的數

e.g, 55  56  22  三個數拼成一個值最大的數會是 565522

e.g, 7  75 兩個數拼成的值最大的數是 775

本來我以為是把每個數給一個值去排序

e.g, 55 => 5.5,  920 =>9.2

但是這個方法在 7, 75的這個例子就會出錯了

所以新的想法就是兩個數字真的拼在一起比看看到底誰該當前面的

所以只需要利用 std::sort 去處理就好
compare function自己寫

	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	static const int LMAX = 1000000;
	char N[50][LMAX + 1];
	int A[50];
	// returns true if N[i] must come before N[j];
	// returns ((N[i] concat N[j]) > (N[j] concat N[i]))
	bool cmp(int i, int j){
	static char a[LMAX * 2 + 1];
	static char b[LMAX * 2 + 1];
	sprintf(a, "%s%s", N[i], N[j]);
	sprintf(b, "%s%s", N[j], N[i]);
	return strcmp(a, b) > 0;
	}
	int main(){
	int n;
	while(true){
	scanf("%d", &n);
	if(n == 0) return 0;
	for(int i = 0; i < n; i++){
	scanf("%s", N[i]);
	A[i] = i;
	}
	std::sort(A, A + n, cmp);
	for(int i = 0; i < n; i++) {
	fputs(N[A[i]], stdout);
	}
	putchar('\n');
	}
	}

view raw 10905.cpp hosted with ❤ by GitHub