Greedy --- HNU 13320 Please, go first Please, go first Problem's Link: http://acm.hnu.cn/online/?action=problem&type=show&id=13320

Mean: 

n個人一起去滑雪，要坐電梯到山頂，電梯每5分鐘可以送一個人上去。這n個人中有的是組好團一起滑雪的，是以要等到齊了才能開始滑。

但是他們到達電梯下的時間都不是統一的，對于單獨一個人來說，他在山下等和在山上等的時間都是一樣的。

但是對于n個人的集體來說，如果讓他後面的人先上去，這樣可能會更節省時間。

求通過調整上電梯的順序後最多可以節省多少時間。（PS:被這鬼題意坑死 ==||）

analyse:

典型的貪心題。

首先我們來分析未調整之前的狀态：

對于一個人，不管你來得多早，你還是得等到和你一個團的最後來的那個人才能開始滑雪。

這樣時間浪費在哪裡了呢？如果是這種情況：AABBBBBBBBBBBBBBABBB，如果我們變成AAABBBBBBBBBBBBBBBBB，

雖然B團隊的時間沒變，但是對于A團隊來說卻節省了很多時間。要貪心的地方就在這。

如何貪呢？

首先需要明确的是：我們不能把同一個團中最後到的那個人提前（人都還沒到怎麼提），而隻能把中間摻雜的其他團的人提前，

而最優情況肯定是：讓同一個團的盡量聚合在一起，這樣等待的時間才是最少的。

綜合這兩個條件，我們首先求出未調整隊形之前的每種元素的最左邊的的位置。

然後按照這個數組來個字元串排序（1.同一個團隊的人聚合在一起；2.不同團隊之間按照最後的人位置來排序）。

最後對于每個元素，我們求這個元素調整前和調整後的位置之差，累加，最後*5即得答案。

Time complexity: O(N)

Source code:

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-07-26-22.01

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#define  LL long long

#define  ULL unsigned long long

using namespace std;

const int MAXN = 25010;

char s[MAXN];

int orp[125], nrp[125], t, n;

bool cmp( char a, char b ) {return orp[a] < orp[b];}

int main()

{

     ios_base::sync_with_stdio( false );

     cin.tie( 0 );

     cin >> t;

     while( t-- )

     {

           cin >> n >> s;

           for( int i = 0; i < n; ++i ) orp[s[i]] = i;

           sort( s, s + n, cmp );

           for( int i = 0; i < n; ++i ) nrp[s[i]] = i;

           long long ans = 0;

           for( int i = 0; i < n; ++i ) ans += abs( orp[s[i]] - nrp[s[i]] );

           cout << ans * 5 << endl;

     }

     return 0;

}