会议安排——解题报告

会议安排——解题报告"/>

会议安排——解题报告

题目链接：
题目大意：有n个会议需要使用学校的会议室，第i个会议的持续时间为ci，最晚在ti时刻结束。会议室某一时间点只能供一场会议使用，并且一场会议只可以选择取消或者完整的开完。求最多可以安排多少个会议。
题目分析：首先一个很简单的思路，如果没有最晚结束的限制，那么显然直接根据持续时间贪心就完了。但这个时候要限制最晚完成时间。我们分析两种情况：
一：如果我们现在的时间是time，而time+ci<=ti的，那么答案就可以直接+1了，因为可以在时间内完成。
二：如果time+ci>ti。但是我们仍然可以处理。已知现在的答案是ans，而i不能直接放进来，那么要怎样才能让结果更优呢？我们显然可以用原来答案序列中持续时间最大的那一个和这个进行替换。如果还不行，Newtime+ci>ti，说明放入他反而会使答案减小，那么就舍弃。
解题过程：
一：维护一个按ti从大到小排的一个优先队列。
二：遇到可以直接满足条件的，直接插入到队列中，ans++，time+=ti。
三：否则检查若将队首出队，能否使i满足条件并且比之前更优，ans不变，time看情况而定。
下面附上AC代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>using namespace std;
typedef long long ll;
struct node
{ll t1;ll t2;
}e[100010];
ll n;
priority_queue<ll> s;
bool cmp(node x,node y)
{return x.t2<y.t2;
}
int main()
{scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld%lld",&e[i].t2,&e[i].t1);sort(e+1,e+1+n,cmp);ll pos=0,ans=0;for(ll i=1;i<=n;i++){if(pos+e[i].t1<=e[i].t2){s.push(e[i].t1);ans++;pos=pos+e[i].t1;}else{if(!s.empty()){ll temp=s.top();if(temp>e[i].t1){pos-=temp;s.pop();s.push(e[i].t1);pos+=e[i].t1;}}}}printf("%lld",ans);return 0;
}