Sorted Adjacent Differences（CodeForces

B - Sorted Adjacent Differences（CodeForces - 1339B）

題目連結

演算法

思維+貪心

時間複雜度O(nlogn)

1.這道題的題意主要就是讓你對一個數組進行一種特殊的排序，使得陣列中相鄰的兩個數的差的絕對值成非遞減趨勢；

2.剛開始對這道題總是執拗於兩個相等的數在不同位置，如何把它們放到前面這個問題，因為路走歪了，最終無果，沒有思路。後來看了一些關於這道題的解題部落格，豁然開朗。

3.使得陣列中相鄰的兩個數的差的絕對值成非遞減趨勢，怎麼想呢。單純想怎麼從差的絕對值最小到最大變化不太容易想，我們可以反過來想，怎麼由差的絕對值最大到最小變化。什麼時候差的絕對值最大，當然是陣列中的最小值和最大值之間的差的絕對值最大。最小值和次大值之間的差的絕對值大還是最小值和次小值之間的差的絕對值大(或者最大值和次小值的差的絕對值大還是最大值和次大值的絕對值大)，當然是前者。

4.然後在想接下來可能再小的是什麼，當然是次小值和次大值之間的差的絕對值。以此類推，可以的出下面這個式子。

最小值、最大值、次小值、次大值、第三小值、第三大值、...
或者
最大值、最小值、次大值、次小值、第三大值、第三小值、...

注意上面的式子只是為了好理解才按照這個順序寫的，最終輸出的時候不要忘了把它倒過來(不知道為啥請看題意)。

5.列出了式子後，那麼思考一下什麼時候才到頭呢，即到哪裡結束呢？

對於偶數個數的陣列來講，即最終達到處於中間的那兩個數；

對於奇數個數的陣列來講，即最終到達處於中間的那一個數。

所以要特判一下。這也是為什麼前面一開始就說要將題意倒過來想，否則直接想出從中間向兩邊展開這個思路不太容易。

6.所以最終得出的思路是先對陣列排序，然後從中間向兩邊展開輸出。

C++程式碼

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int t, n;
int a[N];
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 0; i < n; i++)
            cin >> a[i];
        sort(a, a + n);
        /*
            n = 5
            0,1,2,3,4
            n = 4
            0,1,2,3
        */
        int l, r;
        if(n % 2 == 1)
        {
            cout << a[n/2] << " ";
            l = n / 2 - 1, r = n / 2 + 1;
        }
        else
            l = n / 2 - 1, r = n / 2;
        while(l >= 0 && r < n)
        {
            //cout << a[r] << " " << a[l] << " ";
            cout << a[l] << " " << a[r] << " ";
            //上面這兩個式子用哪個都可以
            ++r;
            --l;
        }
        puts("");
    }
    return 0;
}