洛谷 P2123 皇后游戏 题解【贪心】【数学】

作者: wjyyy 分类: 数学,解题报告,贪心 发布时间: 2018-08-06 22:03

点击量:21

 

    原来排序的条件可以并不线性。。。

 

题目背景

还记得NOIP 2012提高组Day1的国王游戏吗?时光飞逝,光阴荏苒,两年过去了。国王游戏早已过时,如今已被皇后游戏取代,请你来解决类似于国王游戏的另一个问题。

 

题目描述

皇后有\(n\)位大臣,每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临,皇后决定为\(n\)位大臣颁发奖金,其中第\(i\)位大臣所获得的奖金数目为第\(i-1\)位大臣所获得奖金数目与前\(i\)位大臣左手上的数的和的较大值再加上第\(i\)位大臣右手上的数。

 

形式化地讲:我们设第\(i\)位大臣左手上的正整数为\(a_i\),右手上的正整数为\(b_i\),则第\(i\)位大臣获得的奖金数目为\(c_i\)可以表达为:

$$c_i\left\{\begin{aligned}a_1+b_i& & i=1 \\ \max \{ c_{i-1},\sum_{j=1}^{i}a_j\} & & 2\le i\le n\end{aligned}\right.$$

当然,吝啬的皇后并不希望太多的奖金被发给大臣,所以她想请你来重新安排一下队伍的顺序,使得获得奖金最多的大臣,所获奖金数目尽可能的少。

 

注意:重新安排队伍并不意味着一定要打乱顺序,我们允许不改变任何一位大臣的位置。

输入输出格式

输入格式:

第一行包含一个正整数\(T\),表示测试数据的组数。

 

接下来\(T\)个部分,每个部分的第一行包含一个正整数\(n\),表示大臣的数目。

 

每个部分接下来\(n\)行中,每行两个正整数,分别为\(a_i\)和\(b_i\),含义如上文所述。

 

输出格式:

共\(T\)行,每行包含一个整数,表示获得奖金最多的大臣所获得的奖金数目。

 

输入输出样例

输入样例#1:

1
3
4 1
2 2
1 2

输出样例#1:

8

输入样例#2:

2
5
85 100
95 99
76 87
60 97
79 85
12
9 68
18 45
52 61
39 83
63 67
45 99
52 54
82 100
23 54
99 94
63 100
52 68

输出样例#2:

528
902

说明

按照 1、2、3 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 10;

按照 1、3、2 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 9;

按照 2、1、3 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 9;

按照 2、3、1 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 8;

按照 3、1、2 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 9;

按照 3、2、1 这样排列队伍,获得最多奖金的大臣获得奖金的数目为 8。

当按照 3、2、1 这样排列队伍时,三位大臣左右手的数分别为:(1, 2)、(2, 2)、(4, 1)

第 1 位大臣获得的奖金为 1 + 2 = 3;

第 2 位大臣获得的奖金为 max{3, 3} + 2 = 5;

第 3 为大臣获得的奖金为 max{5, 7} + 1 = 8。

对于全部测试数据满足:\(T\le 10,\ 1\le n\le 20000,\ 1\le a_i, b_i\le 10^9\)。

 

题解:

    动手推式子解决一切!

 

    一开始想过一些贪心,比如说\(a_i+b_i\)升序,\(a_i-b_i\)升序等等,发现都能过样例但是交上去GG。推了公式才知道,两个数谁先谁后是要互相关联的

 

    首先我们可以知道,得到奖金最多的一定是最后一个大臣,因为他至少有一个\(b_n\)的加成。我们只要贪出来(说得容易)直接输出最后一个数的答案就可以了。

 

    假设一共只有两个大臣,我们会怎么排序?设两个人的数分别为\(a_1,b_1,a_2,b_2\)。当1号大臣在前面,则2号大臣的得分是$$c_2=\max \{ a_1+a_2,a_1+b_1\}+b_2=\max \{ a _2,b_1\} +a_1+b_2$$

    当2号大臣在前面,则1号大臣的得分是$$c_1=\max\{ a_1,b_2\} +a_2+b_1$$。

    对于每一对大臣,我们都想让排在后面的尽可能小,因为答案在最后面产生,所以在综合比较两个大臣上面的两个信息时,把\(c\)较小的那个大臣放在后面,对后面产生的影响就尽可能地小了。因此我们在比较相邻两个元素排序时,按照上面的式子逆序比较,排完序后模拟输出最后一名大臣的得分就是最终答案了。

 

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
struct minist
{
    long long a,b;
    friend bool operator <(minist a,minist b)
    {
        return a.a+b.b+max(a.b,b.a)<a.b+b.a+max(a.a,b.b);//注意上面移项了(好看)
    }
}a[20100];
long long pnt[20100];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld%lld",&a[i].a,&a[i].b);
        std::sort(a+1,a+1+n);
        long long sum=a[1].a;
        pnt[1]=a[1].a+a[1].b;
        for(int i=2;i<=n;i++)
        {
            sum+=a[i].a;
            pnt[i]=std::max(pnt[i-1],sum)+a[i].b;//直接模拟
        }
        printf("%lld\n",pnt[n]);
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */