正文

江南大学第三届程序设计竞赛K题 - Cun Tou Gaming - [贪心+堆]

IP云
IP云V管理员/0 阅读
11/29
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

描述

CTG(Cun Tou Gaming) 是我校的一支 LOL 战队，他们参加比赛总是可以拿到冠军，因为每次都只有他们一支队伍参赛，所以只需要去签个到就可以直接夺冠并领取奖金。现在有 n 场比赛可以让他们选择，每场比赛都有各自的截止日期 d 和奖金 r ，而 CTG 战队必须在截止日期之前（包括截止日期当天）去参赛才可以拿到奖金。由于签到是一项很辛苦的工作所以战队一天只能参加一场比赛。现在要你设计出一种参赛方案，使他们可以拿到最多的奖金。

Input

有多组样例，第一行一个整数 T(T≤10) ，表示 T 组样例，对于每组样例：

第一行给出一个整数 n 表示有 n(n≤105) 场比赛可以参加。

接下来的 n 行，每行由 d 和 r 组成 (d,r≤109) ，分别表示截止日期和奖金数。

Output

输出 T 行。

每行即为该组测试中可以拿到的最多奖金数，保证答案在long long int的范围内。

Examples

Input 

2

3

2 10

2 15

3 20

3

2 10

1 50

1 40

Output 

45

60

这题就是我在http://www.cnblogs.com/dilthey/p/7859007.html里说的那道题目。

AC代码： 

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

struct Game{

    int d,r;

    bool operator < (const Game& oth)const{return oth.r<r;}

}game[+];

bool cmp(Game a,Game b){return a.d<b.d;}

int n;

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=;i<n;i++) scanf("%d%d",&game[i].d,&game[i].r);

        sort(game,game+n,cmp);

        //for(int i=0;i<n;i++) printf("%d %d\n",game[i].d,game[i].r);

        priority_queue<Game> heap;

        for(int i=;i<n;i++)

        {

            if(game[i].d>heap.size()) heap.push(game[i]);

            else

            {

                Game t=heap.top();

                if(game[i].r>t.r)

                {

                    heap.pop();

                    heap.push(game[i]);

                }

            }

        }

        long long ans=;

        while(!heap.empty())

        {

            //printf("%d %d\n",heap.top().d,heap.top().r);

            ans+=heap.top().r;

            heap.pop();

        }

        printf("%lld\n",ans);

    }

}

附测试数据： 

------Input------

8

3

2 10

2 15

3 20

3

2 10

1 50

1 40

7

4 20

2 60

4 70

3 40

1 30

4 50

6 10

2000

690 129437

444 236120

510 13552

487 376961

8 135813

576 117668

809 256728

790 282625

950 397291

831 46129

621 364410

47 314380

589 343421

907 243865

393 347616

531 365208

725 111070

20 66761

265 353077

767 289700

198 157768

629 101735

634 170788

392 93341

791 289334

259 24363

514 183483

249 342201

379 342490

450 25143

634 106233

11 382625

735 289909

954 206382

691 298898

545 332033

222 100879

506 81493

23 347615

310 35

------Answer-----

45

60

230

299340856

4706131694

298231962423

3417359679513

4671715304676

相关阅读

目录[+]