U68464 滑稽树上滑稽果（guo）

题目描述

小小迪有 n 个约会对象，每个对象有一个约会时长 p[i]，小小迪想尽可能多的去完成他的约会(假设小小迪可以瞬移)，每个对象还有一个忍耐时间 q[i]，如果小小迪没有在这个时间前去赴约并完成约会(<=q[i])，那么她就会离开。你能帮帮他嘛？

输入输出格式

输入格式：

第一行 1 个数字 n 含义如题。接下来 n 行，一行两个数字 p[i],q[i]含义如题

输出格式：

一行一个数字表示小小迪最多能见多少个约会对象。。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于 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

*/

巴特西

U68464 滑稽树上滑稽果（guo）

U68464 滑稽树上滑稽果（guo）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章