Codeforces Round #642 (Div. 3)D. Constructing the Array（广度优先搜索）数据结构与算法amazingee的博客-

原题链接
题意：
给你一个长度为n的数组a初始元素全为0，每次把含0最多的子序列的中间元素设为当前的操作次数，输出最后不含0的a数组内所有元素。
思路：
一开始看到就感觉和归并排序和快速排序的写法差不多，分区间去弄。就写了以下发现深搜没写出来，没法区分区间内0的个数。既然深搜不行，另一个搜索就是广搜了，普通的队列是不行的，因为这里是先对含0最多并且靠左边的区间操作。那么就用优先队列定义以下优先级就可以了。比赛的时候没写错了很可惜。。
代码：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int N=2e5+10; int step=0,n; struct node { int l,r; node(int left=0,int right=0):l(left),r(right){} bool operator<(const node &a)const { int s1=r-l+1; int s2=a.r-a.l+1; if(s1==s2) return l>a.l;//含0一样多就优先靠左边 return (r-l+1)<(a.r-a.l+1);//含0多优先 } }; int a[N]; int main() {     ios::sync_with_stdio(0);     cin.tie(0);cout.tie(0); int t;     cin>>t; while(t--) {         step=0;         cin>>n;         priority_queue<node>q;         q.push(node(1,n)); while(!q.empty()) {             node u=q.top();             q.pop(); int l=u.l,r=u.r,mid; if((r-l+1)%2==0) mid=(l+r-1)/2; else mid=(l+r)/2;             a[mid]=++step; if(l<=mid-1) q.push(node(l,mid-1));//区间存在就入队 if(r>=mid+1) q.push(node(mid+1,r)); } for(int i=1;i<=n;i++) cout<<a[i]<<" ";         cout<<endl; } return 0; }