來(lái)遲了來(lái)遲了，忘寫了。
我們來(lái)看看這道卡了本蒟蒻3個(gè)小時(shí)的題。
傳送門luoguP7913廊橋分配
題目大意：分為了國(guó)內(nèi)和國(guó)外兩部分，飛機(jī)來(lái)了要么停廊橋要么走，有空位一定停，且停最小的，要如何分配廊橋才能使停的飛機(jī)數(shù)最大。
首先我們要知道一個(gè)事實(shí)：

對(duì)于n架飛機(jī)，有無(wú)數(shù)個(gè)廊橋，其中的一架飛機(jī)k，能夠停在廊橋的要求是總的廊橋數(shù)大于等于從第一架來(lái)的飛機(jī)到它飛來(lái)時(shí)使它能停到廊橋的廊橋數(shù)。
換而言之，對(duì)于某一架飛機(jī)，使它能停靠的廊橋數(shù)與有多少個(gè)廊橋無(wú)關(guān)。
至于為什么，我們可以思考：
盡管有無(wú)數(shù)個(gè)廊橋，但是飛機(jī)是嚴(yán)格按照停靠在最小的廊橋上，只要能滿足前k架飛機(jī)能全部停廊橋數(shù)，那么其余的廊橋是沒(méi)有用上的。

得到這個(gè)事實(shí)我們可以得到：
可以就用給出的總廊橋數(shù)來(lái)模擬，對(duì)于每一個(gè)廊橋，可以統(tǒng)計(jì)出在這個(gè)廊橋有多少個(gè)飛機(jī)停，所以總飛機(jī)停靠個(gè)數(shù)就是1~k個(gè)廊橋上的飛機(jī)總和，這個(gè)只需要前綴和處理即可，最后枚舉分配給國(guó)內(nèi)，國(guó)外的廊橋數(shù)，并加到一起，更新max即可。
我們應(yīng)該如何模擬飛機(jī)離開和進(jìn)入呢？
這里使用兩個(gè)優(yōu)先隊(duì)列來(lái)分別維護(hù)最小編號(hào)的廊橋和所在哪個(gè)廊橋的飛機(jī)離開時(shí)間。
首先先按飛機(jī)來(lái)的時(shí)間進(jìn)行排序，將編號(hào)最小的廊橋給它，刪除該廊橋，再將它的離開時(shí)間和該廊橋編號(hào)壓入另一小根堆中，并以離開時(shí)間為第一關(guān)鍵字來(lái)排序。
對(duì)于每一架來(lái)的飛機(jī)，比較它來(lái)的時(shí)間和堆中飛機(jī)離開時(shí)間，若離開時(shí)間小于了來(lái)的時(shí)間，那么就說(shuō)明該飛機(jī)已經(jīng)離開，刪除該飛機(jī)，并又將它所在的廊橋編號(hào)壓入堆中，循環(huán)直達(dá)堆頂飛機(jī)的離開時(shí)間大于了它來(lái)的時(shí)間。
然后就又重復(fù)操作，取出最小編號(hào)的廊橋，刪除，將該廊橋和它離開時(shí)間一同壓入堆中即可。
處理完后，我們得到每一廊橋停靠的飛機(jī)數(shù)量，那么統(tǒng)計(jì)前綴和即是有這么多個(gè)廊橋能停靠的飛機(jī)總數(shù)量。枚舉比較即可。
時(shí)間復(fù)雜度O(nlog₂n)
代碼實(shí)現(xiàn)：

#include<bits/stdc++.h> using namespace std;const int N=1e5+5; int n,m1,m2; priority_queue<int>id;//最小廊橋編號(hào) priority_queue<pair<int,int> >q;//飛機(jī)離開時(shí)間和它所在的廊橋編號(hào) int cfa[N],cfb[N];//統(tǒng)計(jì)該廊橋有多少個(gè)飛機(jī)停 struct node {int l,r; }a[N];bool comp(node x,node y) {return x.l<y.l; }int main() {scanf("%d%d%d",&n,&m1,&m2);for(int i=1;i<=m1;i++) scanf("%d%d",&a[i].l,&a[i].r);sort(a+1,a+m1+1,comp);for(int i=1;i<=n;i++) id.push(-i);for(int i=1;i<=m1;i++){while(!q.empty() && -q.top().first<a[i].l)//飛機(jī)已經(jīng)離開 {id.push(-q.top().second);q.pop();}if(!id.empty())//還有廊橋可以分配 {cfa[-id.top()]++;q.push(make_pair(-a[i].r,-id.top()));id.pop();}}for(int i=1;i<=n;i++) cfa[i]+=cfa[i-1];while(!id.empty()) id.pop();while(!q.empty()) q.pop();//初始化 for(int i=1;i<=m2;i++) scanf("%d%d",&a[i].l,&a[i].r);sort(a+1,a+m2+1,comp);for(int i=1;i<=n;i++) id.push(-i);for(int i=1;i<=m2;i++){while(!q.empty() && -q.top().first<a[i].l) {id.push(-q.top().second);q.pop();}if(!id.empty()){cfb[-id.top()]++;q.push(make_pair(-a[i].r,-id.top()));id.pop();}}for(int i=1;i<=n;i++) cfb[i]+=cfb[i-1];int ans=0;for(int i=0;i<=n;i++) ans=max(ans,cfa[i]+cfb[n-i]);//枚舉分配給國(guó)內(nèi)國(guó)外多少時(shí)最大 cout<<ans;return 0; }

總結(jié)

以上是生活随笔為你收集整理的CSP-S2021试题T1廊桥分配详讲的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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