题目描述
http://codeforces.com/contest/1339/problem/B
有一个长度为 (n(3le n le 10^5)) 的整数序列 (a_1,a_2,...,a_n(-10^9le a_ile 10^9)) 。
将序列重排序使得 (|a_1-a_2|le|a_2-a_3|le...le|a_{n-1}-a_n|) 。
输出任意一种满足上述条件的排序方式。
解题
这里采用一种类似贪心的策略：
- 序列 (a) 中的最大值与最小值差的绝对值（(|a_{max}-a_{min}|)）一定是序列中最大的；
- 最大值和次小值的差的绝对值一定是第二大的；
- 次大值和次小值的差的绝对值一定是第三大的；
- 以此类推…
我们先将数组按升序排序，使得 (a_1le a_2le...le a_n) 。
然后按照 (a_{(n-k+1)},a_k,...,a_{n-1},a_2,a_n,a_1) 顺序输出，即为所求。
#include<bits/stdc++.h>
#define ll long long
#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag) for(int i=0;i<n&&flag;i++)
#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)
#define frrs(i,j,n,flag) for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag) for(int i=n-1;i>=j&&flag;i--)
#define arend(i,n) ((i!=n-1)?" ":"n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end) for(auto it = begin;it!=end;it++) cout<<*it<<arend(it,end);
#define log_this(name,value) cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int to_int(string s) {stringstream ss;ss<<s;int a;ss>>a;return a;}
string to_str(double a) {stringstream ss;ss<<a;return ss.str();}
ll a[1*e5];
ll ans[1*e5];
int main(){
cin.tie(0);
//ios::sync_with_stdio(false);
//cout<<setiosflags(ios::fixed)<<setprecision(0);
//freopen("1.out","w",stdout);
int t;
while(cin>>t){
while(t--){
int n;
cin>>n;
fr(i,n){
cin>>a[i];
}
sort(a,a+n);
int tail = 0;
int b = 0,e = n-1;
while(b<=e){
ans[tail++] = a[b];
if(b!=e) ans[tail++] = a[e];
b++,e--;
}
r_frr(i,0,n){
cout<<ans[i]<<" ";
}
cout<<endl;
}
}
return 0;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
