[經典算法]字符串的排序 (tyvj 1101)

試題：tyvj 1101  （http://tyvj.cpwz.cn/Problem_Show.asp?id=1101）

【題目大意】
給你N(N<=10000)字符串，每個字符串長度小於256，把他們按字典序排序並輸出。

【分析】
C++的快排不是用來吃白飯的～直接調用C++的快排函數，0 ms 無壓力。
為什麼還有很多人會超時啊～

	VijosNT Mini 2.0.5.6 #01: Accepted (0ms, 1212KB) #02: Accepted (0ms, 1036KB) #03: Accepted (0ms, 1192KB) #04: Accepted (0ms, 880KB) #05: Accepted (0ms, 1020KB) #06: Accepted (0ms, 760KB) #07: Accepted (0ms, 528KB) #08: Accepted (0ms, 452KB) #09: Accepted (0ms, 584KB) #10: Accepted (0ms, 1084KB) Accepted / 100 / 0ms / 1212KB

[RMQ問題]OI練習題：綿延的山峰 climb 解題報告

Title: 延綿的山峰 傳送門

Input: climb.in

Output: climb.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★★

問題描述
 

有一座延綿不斷、跌宕起伏的山，最低處海拔為0，最高處海拔不超過8848米，從這座山的一端走到另一端的過程中，每走1米海拔就升高或降低1米。有Q個登山隊計劃在這座山的不同區段登山，當他們攀到各自區段的最高峯時，就會插上隊旗。請你寫一個程序找出他們插旗的高度。

經典算法：歸併操作 和 歸併排序 merge & merge sort

歸併操作就是把兩個已經有序的數組合併為一個數組的過程。
廢話不多說了，直接上代碼。如果不會輕看維基百科。

C++语言: Codee#24222

//歸併操作（merge）
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;   
int A[1000],B[1000];
int C[2000];
int N;

void merge() 
{ 
    int p=0;
    int i=1,j=1;
    while(i<=N&&j<=N) 
    { 
        if(A[i]<B[j]) 
        { 
            C[++p]=A[i++]; 
        } 
        else  
        { 
            C[++p]=B[j++]; 
        } 
    } 
    while(i<=N) C[++p]=A[i++]; 
    while(j<=N) C[++p]=B[j++]; 
}

int main()
{
    freopen("merge.in","r",stdin);
    freopen("merge.out","w",stdout);

    cin>>N;
    for (int i=1;i<=N;i++)
        cin>>A[i];
    for (int i=1;i<=N;i++)
        cin>>B[i];
    merge();
   
    for (int i=1;i<=2*N;i++)
        cout<<C[i]<<" ";
   
    return 0;
}

通過歸併操作，我們可以實現歸併排序（Merge Sort）。歸併排序是遞歸排序算法，使用了分治、二分的思想，把一個數組分為兩個部分，把這每個部分再分為兩個部分，就這樣一次一次的分下去，然後再把它們一次通過歸併操作合併起來，最後完成排序操作。

例題：通過歸併排序尋找逆序對