成都百度推广的关键词,深圳网站快速排名优化,做一年的网站维护价格,个人网站首页设计欣赏正题
题目链接:http://noi.ac/contest/266/problem/795 题目大意 nnn个人第iii个巡逻一次aia_iai秒#xff0c;休息至少bib_ibi秒。 要求
任意时刻都有人巡逻在一个人的两次相邻的巡逻直接不能有另一个人巡逻两次。 解题思路
对于性质二我们发现就是在nnn个人里选择最少…正题
题目链接:http://noi.ac/contest/266/problem/795 题目大意
nnn个人第iii个巡逻一次aia_iai秒休息至少bib_ibi秒。 要求
任意时刻都有人巡逻在一个人的两次相邻的巡逻直接不能有另一个人巡逻两次。 解题思路
对于性质二我们发现就是在nnn个人里选择最少的人轮流巡逻使得任意时刻都有人巡逻。
我们考虑贪心将人按照bib_ibi排序然后枚举就好了这样我们就确定了最大的bib_ibi所以我们要求前面的最大的数的和使得它的和足够就好了。
但是这样我们会发现有许多问题因为这个人两次巡逻的间隔是不计算自己的巡逻时间的 也就是sum−aibi⇒sumbiaisum-a_ib_i\Rightarrow sumb_ia_isum−aibi⇒sumbiai
所以我们改为按照biaib_ia_ibiai排序就好了然后对顶堆维护前若干个最大值使得他们的和满足max{biai}max\{b_ia_i\}max{biai} codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N5e510;
struct node{ll t,b;
}a[N];
ll n,sum,z,ans2147483647;
priority_queuell q1,q2;
bool cmp(node x,node y)
{return x.by.b?x.ty.t:x.by.b;}
int main()
{//freopen(data.in,r,stdin);scanf(%lld,n);for(ll i1;in;i){scanf(%lld%lld,a[i].t,a[i].b);a[i].ba[i].t;}sort(a1,a1n,cmp);for(ll i1;in;i){if(q1.empty()||a[i].t-q1.top()){q1.push(-a[i].t);suma[i].t;z;}else q2.push(a[i].t);while(!q1.empty()suma[i].b){sumq1.top();z--;q2.push(-q1.top());q1.pop();}while(!q2.empty()suma[i].b){sumq2.top();z;q1.push(-q2.top());q2.pop();}if(suma[i].b){ansmin(ans,z);}}if(ans2147483647) printf(-1);else printf(%lld,ans);
}
