https://codeforces.com/contest/1579/problem/E1
算法的本质思路是贪心
第一点看到n特别大,又是求最优解问题,多手玩几个数字就好了
在实现上要会写小根堆,
赛场上a了,赛后被卡在test 14
#include<bits/stdc++.h> using namespace std; const int maxn=1e6; int n,vis[maxn]; struct node{ int id,val; bool operator > (const node tmp)const{ return val>tmp.val; } }a[maxn]; priority_queue<node,vector<node>,greater<node> >q; void after( ) { memset(vis,0,sizeof(vis)); while(!q.empty()) { q.pop() ; } } int main( ) { //freopen("crazylys.in","r",stdin); int t; cin>>t; while(t--) { int point; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].val; if(a[i].val==1) { point=i; } } for(int i=1;i<=point;i++) { node son; son.id=i; son.val=a[i].val; q.push(son); } int ok=1; while(ok==1) { node son; for(;;) { son=q.top(); if(son.id>point) { q.pop(); } else { printf("%d ",son.val); vis[son.id]=1; point=son.id; q.pop(); break; } } if(point==1) { ok=0;break; } } for(int i=1;i<=n;i++) { if(vis[i]==0) { printf("%d ",a[i].val); } } printf("\n"); after( ); } }