线性推,开数组太麻烦,可以用指针
代码:
#include <iostream> #include <cstdio> #include <queue> using namespace std; const int N = 100010; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();} return x * f; } struct node { int val,vis; node *nxt , *fa; node () {val = vis = 0;nxt = fa = NULL;} }*root; struct num { int val; node *p; friend bool operator < (const num & a,const num & b) { return a.val < b.val;} }; int n , cnt; priority_queue<num>q; int main() { #ifdef yilnr #else freopen("ysy.in","r",stdin); freopen("ysy.out","w",stdout); #endif n = read(); node *p = root =new node(); for(int i = 1;i <= n;i ++) { p -> val = read(); q.push( (num) {p -> val,p}); if(i < n) { p -> nxt = new node(); p -> nxt -> fa = p; p = p -> nxt; } } while(cnt != (n >> 1)) { node *p = q.top().p; q.pop(); if(p -> nxt == NULL) continue; if(p -> vis || p -> nxt -> vis) continue; printf("%d %d ",p -> val,p -> nxt -> val); cnt ++; if(p -> fa && p -> nxt && p -> nxt -> nxt) { p -> nxt -> nxt -> fa = p -> fa; p -> fa -> nxt = p -> nxt -> nxt; } p -> vis = 1; p -> nxt -> vis = 1; } fclose(stdin); fclose(stdout); return 0; } /* 12 4 3 6 10 12 11 5 8 2 1 7 9 */