題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長(zhǎng)度為 n ，初始時(shí)全部為 0 的數(shù)組 a ，后續(xù)進(jìn)行 n 次操作，每次操作找到最長(zhǎng)的連續(xù) 0 ，如果有多個(gè)則選擇位置最靠左邊的，將這組連續(xù)?0 的，最中間位置的數(shù)賦值為 i ，i 為第 i 次操作，輸出最后的數(shù)列

題目分析：一開(kāi)始沒(méi)什么思路，用線段樹(shù)區(qū)間合并暴力模擬的，果不其然 TLE 了，其實(shí)自己手算模擬幾次就會(huì)發(fā)現(xiàn)，每個(gè)位置至多會(huì)被遍歷到一次，且是按照深度擴(kuò)展的，所以我們可以用 bfs + 優(yōu)先隊(duì)列 不斷擴(kuò)展就好了，具體實(shí)現(xiàn)可以看代碼

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int ans[N],pos;struct Node {int l,r;Node(int l,int r):l(l),r(r){}bool operator<(const Node& t)const{if(r-l+1!=t.r-t.l+1)return r-l+1<t.r-t.l+1;return l>t.l;} };void bfs(int l,int r) {priority_queue<Node>q;q.push(Node(l,r));while(q.size()){Node cur=q.top();q.pop();l=cur.l;r=cur.r;int mid=l+r>>1;ans[mid]=++pos;if(l==r)continue;if(mid+1<=r)q.push(Node(mid+1,r));if(l<=mid-1)q.push(Node(l,mid-1));} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;scanf("%d",&n);pos=0;bfs(1,n);for(int i=1;i<=n;i++)printf("%d ",ans[i]);puts("");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1353D Constructing the Array(bfs)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。