U68464 滑稽树上滑稽果（guo）
题目描述
小小迪有 n 个约会对象，每个对象有一个约会时长 p[i]，小小迪 想尽可能多的去完成他的约会(假设小小迪可以瞬移)，每个对象还有 一个忍耐时间 q[i]，如果小小迪没有在这个时间前去赴约并完成约 会(<=q[i])，那么她就会离开。你能帮帮他嘛？
输入输出格式
输入格式：
第一行 1 个数字 n 含义如题。 接下来 n 行，一行两个数字 p[i],q[i]含义如题
输出格式：
一行一个数字表示小小迪最多能见多少个约会对象。。
输入输出样例
输入样例#1：
9
9 14
2 15
7 9
7 11
13 15
11 13
5 9
1 7
3 9
输出样例#1：
4
说明
对于 30%的数据，n<=5000;
对于 100%的数据，n<=500000
sol：一道十分不错的题
考虑贪心：首先策略是要尽量取得多，即在能取的情况下尽量取，其次是在取相同的数量时结束时间尽量早，这个东西的维护挺巧妙的，开一个大根堆，堆顶是花费最多的那个时间，每次如果不能取得话就比较一下堆顶和当前的时间；
Ps：因为开始对于结束时间排序了一下，自己yy一下发现如果被替换的时间大于当前的时间，当前一定可以有贡献（因为这道题要求的是当前用的时间+需要用的时间<=限制的时间）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=;
int n;
struct Record
{
ll Time,Limit;
}a[N];
inline bool cmp_Limit(Record p,Record q)
{
return (p.Limit!=q.Limit)?(p.Limit<q.Limit):(p.Time<q.Time);
}
priority_queue<ll>Queue;
int main()
{
freopen("1.in","r",stdin);
int i,ans=;
ll Used=;
R(n);
for(i=;i<=n;i++)
{
R(a[i].Time); R(a[i].Limit);
}
sort(a+,a+n+,cmp_Limit);
for(i=;i<=n;i++)
{
if(a[i].Time+Used>a[i].Limit)
{
if(Queue.empty()) continue;
int tim=Queue.top();
if(tim>a[i].Time)
{
Used=Used-tim+a[i].Time;
Queue.pop();
Queue.push(a[i].Time);;
}
}
else
{
Used+=a[i].Time;
Queue.push(a[i].Time);
ans++;
}
}
Wl(ans);
return ;
}
/*
input
9
9 14
2 15
7 9
7 11
13 15
11 13
5 9
1 7
3 9
output
4
*/