TIOJ 1967 千湖之路4

　　先說想法，再說作法，最後說證明。

想法：

　　既然要配N對，然後每對又要相鄰，感覺好難QQ，

　　但是題目都說有N*(N+1)個人了，感覺好像很多，

　　所以就試試看，把所有人分成Ｎ段，然後每段取一對？！

　　所以現在總共N段，每段N+1人。

作法：

　　由於取的一對兩兩數值大小要相鄰，那不如從小的配對開始取，

　　我們對人，從左到右編號0~N*(N+1)-1，接下來，按照每個人的大陸人指數排序，

　　我們從大陸人指數小的人開始看，

　　假設現在他編號是X，他處在第B段(    B=X/(N+1)    )，

　　我們看看第B段有沒有人，

　　要是沒有人，我們說現在X佔據第B段（第B段的人是X），

　　那如果有人呢？

　　那太好了，我們可以把當下佔據B的人和X湊成一對。

　　然後把所有剛剛所有被占據的區段清空。

　　然後封鎖B區段，讓以後所有人再也進不來。

　　最後，既然有N段，那麼自然會湊成N對。

證明：

　　每次我們想要找到新的一對時，都是看看該區段有沒有人，

　　按照鴿籠原理，既然我們只有N段，那麼當我看完N人若是沒有配對，

　　那N個人肯定是一人占據一段，

　　所以第N+1人不管屬於哪段，都會有人跟他配對（好幸福），

　　所以我們知道，每N+1人，至少能湊出一對，

　　而剛好總人數就是N*(N+1)可以湊出N對

以下附code

#include <bits/stdc++.h>
using namespace std;
#define SZ(x) x.size()
#define IOS do{ios_base::sync_with_stdio(0); cin.tie(0);}while(0)
const int INF=1e9+7;
const int MAX=1000;
int arr[MAX*(MAX+1)],box[MAX*(MAX+1)],las[MAX],ans[MAX*2],p,n;
bitset<MAX> used;
bool cmp(int a,int b){
 return arr[a]<arr[b];
}
int main(){
 IOS;
 cin>>n;
 int nn=n*(n+1);
 for(int i=0;i<nn;i++){
  cin>>arr[i];
  box[i]=i;
 }
 memset(las,-1,n*4);
 used.reset();
 sort(box,box+nn,cmp);
 stack<int> st; while(SZ(st)) st.pop();
 for(int i=0;i<nn;i++){
  int x=box[i],b=x/(n+1);
  if(used[b]) continue;
  if(las[b]==-1){
   las[b]=x;
   st.push(b);
  }
  else{
   ans[p++]=las[b];
   ans[p++]=x;
   used[b]=1;
   while(SZ(st)) las[st.top()]=-1,st.pop();
  }
 }
 sort(ans,ans+p);
 for(int i=0;i<p;++i){
  if(i) cout<< ' ';
  cout<<ans[i];
 }
 cout<< '\n';
 return 0;
}