银河美术馆-Beautyyu

这里是Beautyyu言醴的独立博客
越是孤单 越是向前 越是疲倦 越不能歇
——《未来的我》

BeautyYu言醴's avatar BeautyYu言醴

Luogu2123皇后游戏|题解

我们设第 i 位大臣左手上的正整数为 ai,右手上的正整数为 bi,则第 i 位大臣获得的奖金数目为 ci可以表达为:

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

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

悠娴之邀写的一篇题解

显然我们发现,数列$c$是一个递增数列,”获得奖金最多的大臣”实际上就是最后一位大臣.

设$a_0=b_0=0$,则第$i(i\geq 1)$位大臣获得奖金$f_1$
$$
=max(c_{i-1},\sum_{j=1}^i a_j)+b_i
$$

$$
=max(max(c_{i-2},\sum_{j=1}^{i-1}a_j)+b_{i-1},\sum_{j=1}^{i}a_j)+b_i
$$

$\sum_{i=m}^{n}a_i$意为数列$a$中从第$m$项到第$n$项的累和

若我们交换第$i$和$i-1$两位大臣的位置,则当前后面这位大臣(即原先第$i-1$位)所获奖金$f_2$
$$
=max(max(c_{i-2},\sum_{j=1}^{i-2}a_j+a_i)+b_i,\sum_{j=1}^i a_j)+b_{i-1}
$$
假定交换两人之前的排列方式是更优的,也就是说
$$
f_1<f_2
$$
展开得
$$
max(max(c_{i-2},\sum_{j=1}^{i-1}a_j)+b_{i-1},\sum_{j=1}^{i}a_j)+b_i<max(max(c_{i-2},\sum_{j=1}^{i-2}a_j+a_i)+b_i,\sum_{j=1}^i a_j)+b_{i-1}
$$
再展开得
$$
max(c_{i-2}+b_{i-1}+b_{i},\sum_{j=1}^{i-1}a_j+b_{i-1}+b_i,\sum_{j=1}^ia_j+b_i)<max(c_{i-2}+b_i+b_{i-1},\sum_{j=1}^{i-2}a_j+a_i+b_i+b_{i-1},\sum_{j=1}^{i}a_j+b_{i-1})
$$

容易证明,$max(a,b)<max(a,c)$等价于$b<c$

原不等式两边同时消去$c_{i-2}+b_{i-1}+b_{i}$
$$
max(\sum_{j=1}^{i-1}a_j+b_{i-1}+b_i,\sum_{j=1}^ia_j+b_i)<max(\sum_{j=1}^{i-2}a_j+a_i+b_i+b_{i-1},\sum_{j=1}^{i}a_j+b_{i-1})
$$
两边同时减去$\sum_{j=1}^ia_j$
$$
max(-a_i+b_{i-1}+b_i,b_i)<max(-a_{i-1}+b_i+b_{i-1},b_{i-1})
$$
两边同时减去$(b_i+b_{i-1})$
$$
max(-a_i,-b_{i-1})<max(-a_{i-1},-b_i)
$$
去负号
$$
min(a_i,b_{i-1})>min(a_{i-1},b_i)
$$
至此,我们得到了一个形式较为简单的,只与相邻两项有关的不等式.根据这个不等式进行排序即可.

完整代码如下:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#define LL long long
using namespace std;
LL n;
struct pwp{
        LL a,b;
        bool operator < (const pwp &qwq)const{
                return min(qwq.a,b) > min(a,qwq.b);
        }
}arr[40000];
//Both overloading operator function and defining a compare function are correct
bool cmp(const pwp &al,const pwp &be){
    //"al" is short for "alpha","be" is short for "beta"
    return min(be.a,al.b) > min(al.a,be.b);
}
int main (){
        LL T;
        cin >> T;
        arr[0] = (pwp){0,0};
        while(T --){
                LL ans = 0,sum_ = 0;
                cin >> n;
                for (LL i = 1;i <= n;++ i)
                        scanf("%lld%lld",&arr[i].a,&arr[i].b);
                sort(arr + 1,arr + 1 + n);
                for (LL i = 1;i <= n;++ i){
                        sum_ += arr[i].a;
                        ans = max(ans,sum_) + arr[i].b; 
                }
                printf("%lld\n",ans);
        }
        return 0;
}

考虑另一点:原式为什么不是$f_1\leq f_2$?

  1. 比较函数cmp<定义的是严格小于,不能用小于等于去定义它们
  2. $max(a,b)\leq max(a,c)$不等价于$b\leq c$

求解这类”求某方案,使某值最大/小”的贪心问题可以考虑假定一个最佳方案,然后对该方案进行略微改动,列不等式,观察不等式得到贪心策略.

这种方法称为”微调法”(似乎?),在很多贪心问题上都很实用.

文结.

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
如非注明,所有图片均来源于网络,如若侵删
Link to this article: https://blog.beautyyuyanli.ml/2018/12/17/2018-12-17-Luogu2123皇后游戏题解/