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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/107672.html
標籤：其他