先对序列排个序。
例如：1 2 3 4 5 6 7
我们把序列分成两半，前一半是1 2 3 4，后一半是5 6 7
然后，我们从前一半取最小的一个，再从后一半取最小的一个。。一直操作下去就能构造出答案了。
由此也可以看到，不可能出现Impossible的情况。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn=1000+10; int n; int a[maxn]; bool flag[maxn]; int ans[maxn]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); int st1=1,st2=(n+1)/2+1; int tot=0; while(1) { ++tot; if(tot%2==1) ans[tot]=a[st1++]; else ans[tot]=a[st2++]; if(tot==n) break; } for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf("\n"); return 0; }
原文：http://www.cnblogs.com/zufezzt/p/5322304.html