正題

題目鏈接:http://noi.ac/contest/266/problem/795

---

題目大意

$n$個人第$i$個巡邏一次$a_i$秒，休息至少$b_i$秒。
要求

任意時刻都有人巡邏

在一個人的兩次相鄰的巡邏直接不能有另一個人巡邏兩次。

---

解題思路

對于性質二我們發現就是在$n$個人里選擇最少的人輪流巡邏使得任意時刻都有人巡邏。

我們考慮貪心，將人按照$b_i$排序，然后枚舉就好了，這樣我們就確定了最大的$b_i$，所以我們要求前面的最大的數的和使得它的和足夠就好了。

但是這樣我們會發現有許多問題，因為這個人兩次巡邏的間隔是不計算自己的巡邏時間的，
也就是$sum?a_i>b_i?sum>b_i+a_i$

所以我們改為按照$b_i+a_i$排序就好了，然后對頂堆維護前若干個最大值使得他們的和滿足$max\{b_i+a_i\}$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const ll N=5e5+10; struct node{ll t,b; }a[N]; ll n,sum,z,ans=2147483647; priority_queue<ll> q1,q2; bool cmp(node x,node y) {return x.b==y.b?x.t<y.t:x.b<y.b;} int main() {//freopen("data.in","r",stdin);scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld%lld",&a[i].t,&a[i].b);a[i].b+=a[i].t;}sort(a+1,a+1+n,cmp);for(ll i=1;i<=n;i++){if(q1.empty()||a[i].t>-q1.top()){q1.push(-a[i].t);sum+=a[i].t;z++;}else q2.push(a[i].t);while(!q1.empty()&&sum>=a[i].b){sum+=q1.top();z--;q2.push(-q1.top());q1.pop();}while(!q2.empty()&&sum<a[i].b){sum+=q2.top();z++;q1.push(-q2.top());q2.pop();}if(sum>=a[i].b){ans=min(ans,z);}}if(ans==2147483647) printf("-1");else printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的NOI.AC-保镖【贪心,对顶堆】的全部內容，希望文章能夠幫你解決所遇到的問題。

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