題目描述

設有??n?個正整數(shù)??1…??a1?…an?，將它們聯(lián)接成一排，相鄰數(shù)字首尾相接，組成一個最大的整數(shù)。

輸入格式

第一行有一個整數(shù)，表示數(shù)字個數(shù)??n。

第二行有??n?個整數(shù)，表示給出的??n?個整數(shù)???ai?。

輸出格式

一個正整數(shù)，表示最大的整數(shù)

輸入輸出樣例

輸入 #1復制

3
13 312 343

輸出 #1復制

34331213

輸入 #2復制

4
7 13 4 246

輸出 #2復制

7424613

說明/提示

對于全部的測試點，保證?1≤?≤201≤n≤20，1≤??≤1091≤ai?≤109。

今明兩天期末考試，本蒟蒻自忖考得不行，為轉(zhuǎn)移注意力，特地來洛谷更新一下題解?（這是什么神邏輯）?。話說這是本蒟蒻的第一篇題解，也是花了很長時間憋出來的一篇題解（萌新想寫題解真難），但原文講的并不清楚?估計只有我自己能看懂?，此次修改務求讓大伙一看就明白。本題解看著字多，思路還是比較簡單的。

本題解重心在證明。先貼下代碼，非常簡短：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string s[21];int n;
bool cmp(const string &a,const string &b) { // &表示引用
    return (a+b > b+a);
}
int main(void) {
    cin >> n;
    for(int i=1;i<=n;++i) cin >> s[i];
    sort(s+1,s+n+1,cmp);
    for (int i=1;i<=n;++i) cout << s[i];
    return 0;
}

證明之前，我們先定義幾個符號
??￣ab?（a,b是數(shù)字字符串）
表示??+?a+b?也就是把?a和?b連起來寫
???￣abc?（a,b,c都是數(shù)字符串）（當然再多幾個字符串也沒關系，跟上面一個意思）
沒錯，這個東西本來是表示數(shù)字的，現(xiàn)在被我們借過來表示字符串

???a?b?表示正常的?a大于等于?b?（下面這個就是不正常的）
a>=b?a,b是數(shù)字字符串 表示??+???+?a+b?b+a
注意區(qū)分這兩個大于等于！

a*n?a是數(shù)字字符串 n是正整數(shù) 表示把?a連續(xù)寫?n遍形成的很長的字符串

說明了這么幾個奇怪的符號之后，我們正式開始證明。

從代碼中可以看出，我們把?a數(shù)組按這個?>=?符號?降序?排好序，再直接輸出就是正確的答案了。容易發(fā)現(xiàn)，對于任意一種排列方式，只要相鄰的兩個數(shù)不滿足 前面的?>=?后面的（注意這是那個奇怪的大于等于），那么這種排列肯定不是最優(yōu)的。也就是說，對于最優(yōu)排列，肯定有 第一個串?>=?第二個串 第二個串?>=?第三個串 第三個串?>=?第四個串 ... 依此類推。

經(jīng)過這一些簡單的推理，證明的思路實際上很清晰了（千萬不要誤認為證完了）：只需要再證明傳遞性（由a>=b?且?b>=c?能否推出?a>=c)。這是最后的一步，也是關鍵的一步。

先證明一個性質(zhì)： 如果?a>=b，那么?a*n >= b。 （思路：遞推/數(shù)學歸納法）

由a>=b即???￣???￣ab?ba
可知????￣????￣aab?aba?并且????￣????￣aba?baa
從而????￣????￣aab?baa?也就是?a*2>=b

由a*2>=b即????￣????￣aab?baa?又由???￣???￣ab?ba
可知?????￣?????￣aaab?abaa?并且?????￣?????￣abaa?baaa
從而?????￣?????￣aaab?baaa?也就是?a*3>=b

依此類推，便能證得?a*n>=b
類似地，由?a>=b，也可以得到?a>=b*n。 相反，如果?a*n>=b?或者?a>=b*n，也能得到?a>=b。（口胡一個證明，如果不滿足a>=b這個結論，肯定不滿足題設，如果能滿足a>=b這個結論，題設肯定成立。大概是一個反證法？）

有了這個結論，我們只要對?,?,?a,b,c各乘上一個合適的整數(shù)（沒錯就是合適），不難證明傳遞性了。文章來源地址http://www.zghlxwxcb.cn/news/detail-403688.html

原以為修改后能改短，卻發(fā)現(xiàn)它變長了。但是你看我改的這么認真，不點個贊再走嗎？

到了這里，關于P1012 [NOIP1998 提高組] 拼數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！