---

正題

題目鏈接:https://www.luogu.org/problemnew/show/P4989

---

題目大意

一個二進制數兩兩配對，要求

配對的數不能交叉(用同一個區間但不包含)

0在前1在后

要求配對最多的情況下所有配對的距離之和最遠。

---

解題思路

將0視為左括號，1視為右括號，題目變為括號匹配問題。

我們考慮貪心，先是交叉的問題，我們發現如果兩個交叉了，我們讓他們反過來配對(配對方的那個)的話答案并不會改變。所有我們不要考慮交叉問題。

那我們開始做，首先不考慮配對最多，我們可以開一個小根堆，存儲目前所有已經匹配的右括號還有未左括號的位置。然后我們每次到一個右括號時，取出最小的那個與其匹配并計算多出來的代價。然后從新丟入堆中。

這是距離之和最遠，但是配對最多怎么辦，那么我們定義權值，小根堆維護權值。對于已經匹配的右括號我們權值就是它的位置；對于沒有匹配的左括號，我們讓它的權值加上一個$?inf$就可以了。

這樣就可以保證優先匹配沒有匹配的且權值最大。

時間復雜度$O(nlogn)$

---

$code$

#include<cstdio> #include<queue> #include<iostream> using namespace std; struct node{int wz,w; }; bool operator <(const node &a,const node &b) {return a.w<b.w;} priority_queue<node> q; int n,ans,a[1000]; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){char c;cin>>c;a[i]=c-'0';}for(int i=1;i<=n;i++){if(!a[i]) q.push((node){i,233333333-i});else{if(q.empty()) continue;ans+=i-q.top().wz;q.pop();q.push((node){i,-i});}}printf("%d",ans); }

總結

以上是生活随笔為你收集整理的P4989-二进制之谜【堆,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。