【题解】P5462 X龙珠

赛题 #B: P5462 X龙珠 | 满分: 100分

发一个set做法

维护两个set，一个按照顺序排序，一个按照值排序。

每次从大往小取，问题就变成了判断这个最大值后面是否有数，直接查看一下按照顺序排序的该数是否有后继。

编译记得用c++11，请安心食用。

(为了方便理解，按照顺序排序的set写得不够优美)

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

#include<vector>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

typedef pair < int , int > node;

#define x first

#define y second

#define mk make_pair

set < node > s;

set < int ,greater < int > > s1;

int n;

const int maxn=1e5+5;

int arc[maxn];

vector < int > ve;

int main(){

#ifndef ONLINE_JUDGE

      freopen("in.in","r",stdin);

      //freopen("out.out","w",stdout);

#endif

      n=qr();

      for(register int t=1,c;t<=n;++t)

	    s.insert(mk(t,c=qr())),s1.insert(c),arc[c]=t;

      for(register int t=1;t<=n>>1;++t){

	    for(auto it:s1){

		  auto ti=s.find(mk(arc[it],it));

		  if(ti!=s.end()&&++ti!=s.end()){

			auto t1=*ti--;

			auto t2=*ti;

			s.erase(t1);

			s.erase(t2);

			ve.push_back(t2.second);

			ve.push_back(t1.second);

			s1.erase(t1.second);

			s1.erase(t2.second);

			break;

		  }

	    }

      }

      int cnt=0;

      for(auto t:ve) printf("%d%c",t,++cnt==n?'\n':' ');

      return 0;

}

巴特西

【题解】P5462 X龙珠

【题解】P5462 X龙珠

最新文章

热门文章