P2123 皇后游戏 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • Segmentation_fault
    %%%,感谢,我照着正解终于把策略推出来了,但是他的做法我看不懂
  • 雅儿贝德
    写得相当清楚orz
  • kl膜法59改
    感谢巨神,可以说是写得相当清楚了
  • Yygq_Master
    这道题为什么在普及蒟蒻试练场里,本蒟蒻被卡住了
  • 陈学威
    %%%
  • LingFengGold
    %%%%
  • 向noip冲刺
    sb
  • 小黑AWM
    这题黄题不能再多了……
  • 小黑AWM
    (都不用高精……
  • 落寞音箫
    深入人心海星
作者: liuzibujian 更新时间: 2018-08-12 13:27  在Ta的博客查看 举报    299  

洛谷p2123

前言

这是一道省选/NOI-的题目,我认为这道题确实有这么难。很多人认为没有这么难,那是因为他们的做法并不是完全正确的。我看了洛谷仅有的三篇题解,竟然有两篇是有错的。正确的那篇题解在这里。这篇仅有的正解的作者还给出了一组证明另外几篇题解有误的数据,将在后面给出。

也欢迎大家来我的博客

题目大意

有n个大臣,第i位大臣左手的数为$a_i$,右手的数为$b_i$,且$a_i$和$b_i$均为正整数。他能获得的数$c_i$由以下关系给出: 这里写图片描述

求$c_i$最大的大臣的$c_i$最小为多少。

题目思路

乍一看,这题和NOIP 2012 提高组 Day1 的国王游戏很像,做题方法应该也差不多,找出一个排序方法,使得以这样排序得到的序列会使最大的$c_i$最小。观察可知,$c_i$是逐渐递增的。我们用相邻交换法考虑。设某个位置上的大臣编号为i,后面一位大臣的编号为j。设i前面所有大臣的a值之和为x,i前面那一位大臣的c值为y。若不交换,则c值较大的大臣的c值($c_j$)为

$max(max(y,x+a_i)+b_i,x+a_i+a_j)+b_j$

化简后为

$max(y+b_i+b_j,x+a_i+b_i+b_j,x+a_i+a_j+b_j$)

同理,这两位大臣交换后,c值较大的大臣的c值($c_i$)为

$max(y+b_i+b_j,x+a_j+b_i+b_j,x+a_i+a_j+b_i$)

假设不交换更优,则有

$max(y+b_i+b_j,x+a_i+b_i+b_j,x+a_i+a_j+b_j)\leq max(y+b_i+b_j,x+a_j+b_i+b_j,x+a_i+a_j+b_i)$

发现两边都有$y+b_i+b_j$,则可以消去(数学上是不能消去的,但这道题可以,下面会给出证明),

消去后有:

$max(x+a_i+b_i+b_j,x+a_i+a_j+b_j)\leq max(x+a_j+b_i+b_j,x+a_i+a_j+b_i)$

然后可以把x消去:

$max(a_i+b_i+b_j,a_i+a_j+b_j)\leq max(a_j+b_i+b_j,a_i+a_j+b_i)$①

再进行化简:

$max(b_i,a_j)+a_i+b_j\leq max(b_j,a_i)+a_j+b_i$②

移项:

$max(b_i,a_j)-a_j-b_i\leq max(b_j,a_i)-a_i-b_j$③

观察左式,$a_j$和$b_i$中大的数被消掉了,只剩下$a_j$和$b_i$中较小数的相反数,用数学语言表述出来就是$-min(a_j,b_i)$,那么③式可以变成:

$-min(a_j,b_i)\leq-min(a_i,b_j)$④

再把负号处理掉:

$min(a_i,b_j)\leq min(a_j,b_i)$⑤

于是我们得到了一个非常简单的式子。

关于消去$y+b_i+b_j$的证明

本来我是不想写的,但有很多人来问,我就证明一下吧。

把前面的式子概括一下,可变成:

$max(a,c)\leq max(b,c)$①

现在要证明在本题中$c$可以消掉,即该式等价于$a\leq b$②

开始分类讨论:

1.$a\leq b$,满足②式,则$a$和$b$不用交换,同时又满足①式。

2.$a>b$,不满足②式,按照题意,则需要交换$a$和$b$,交换后自然就满足①式了。

综上,在本题中,$y+b_i+b_j$可以消去。

在洛谷AC但是错误的方法

根据得到的⑤式重载小于号(里面不能写小于等于,不然有几个点会RE,原因会在下面讲),然后进行排序。有了排完序的序列,后面只需要模拟求出每个数的c值就行了。

这是我的程序:

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int x,y;
    bool operator <(node a) const
    {
        return min(x,a.y)<min(y,a.x);//不能写<=
    }
}a[20005];
int t,n;
long long c[20005];
int main()
{
    cin>>t;
    for (int k=1;k<=t;k++)
    {
        cin>>n;
        for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
        sort(a+1,a+n+1);
        long long s=0;
        for (int i=1;i<=n;i++)
        {
            s+=a[i].x;
            c[i]=max(c[i-1],s)+a[i].y;
        }
        cout<<c[n]<<'\n';
    }
}

其实不一定要用⑤式进行排序,按照上面的①②③④式进行排序都是可以的,只不过要注意开long long,因为数据很大,加法容易溢出。

这是我用②式写的程序:

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    long long x,y;
    bool operator <(node a) const
    {
        return x+a.y+max(a.x,y)<y+a.x+max(a.y,x);
    }
}a[20005];
int t,n;
long long c[20005];
int main()
{
    cin>>t;
    for (int k=1;k<=t;k++)
    {
        cin>>n;
        for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
        sort(a+1,a+n+1);    
        long long s=0;
        for (int i=1;i<=n;i++)
        {
            s+=a[i].x;
            c[i]=max(c[i-1],s)+a[i].y;
        }
        cout<<c[n]<<'\n';
    }
}

为什么重载小于号时不能加等号

我也是想了好久才想出来的。这其实是你快排没有掌握好,才会加等号。系统自带的排序和手写快排差不多,于是我手写了一下快排。

#include<iostream>
#include<algorithm>
using namespace std;
int n,a[1005];
void qsort(int l,int r)
{
    int x=a[(l+r)/2];
    int i=l,j=r;
    while (i<=j) 
    {
        while (a[i]<=x) 
        {
//          cout<<i<<' '<<a[i]<<'\n';
            i++;
        }
        while (a[j]>=x) j--;
        if (i<=j)
        {
            int t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
            j--;    
        }
    }
    if (l<j) qsort(l,j);
    if (r>i) qsort(i,r);
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    qsort(1,n);
    for (int i=1;i<=n;i++) cout<<a[i]<<' ';
}

重载小于号重载的就是第11行和16行的小于号,让我们看看改成小于等于号会有怎样的结果。你可以把注释掉的那行话的注释符取消掉,输出来。你会发现,它会循环到数组越界之后才会停止(本来开的100000的数组,等了好久才等到它输完,方便起见,改为1000)。所以重载小于号一定不能加等于,不然很容易RE。

为什么这种方法是错的

之前提到的三篇题解中唯一一篇正确的题解的作者提供了一组hack数据: 输入:

2
7
6 3
1 1
7 3
1 1
1 6
1 1
6 10

7
6 10
1 1
6 3
1 1
7 3
1 1
1 6

输出:

26
26

两组数据只是顺序不一样,但用上面的程序输出的结果也是不同的。为什么会这样呢?再具体地分析一下。假设有三位大臣,他们的a[i]和b[i]分别是:

7 3
1 1
1 6

显然,这样可以是排完序后的结果,因为两两之间用条件判断都是等于。这样算出来答案是17。而如果这样排:

1 1
1 6
7 3

答案是12,显然这样更优,但程序却有可能排成17的那种情况。

虽然按条件判断相等的两组数交换一次对后面确实不会产生影响,但可以通过多次交换对最终结果产生影响。

错误的根本原因就是,这个判断条件不满足传递性。

正确解法

写正确解法之前,我先要好好感谢一下那位第一个写正解的大佬,是他的博客和他的数据才引发了我以下的思考。 既然要使排序能满足传递性,就应该想出一个对所有数普遍适用的一个排序条件,而不只针对于相邻的两个数。上面得到的⑤式肯定要被用起来。再仔细观察一下这个式子:

$min(a_i,b_j)\leq min(a_j,b_i)$

可以发现,大概应该和a与b的大小关系有关($a_i$和$b_i$哪个大)。还有,要使一个数排在前面,那么a越小越好,b越大越好。我们先按a与b的大小关系把所有数据分为三大组,然后开始讨论:

1.当$a_i<b_i$,$a_j<b_j$时,$a_i\leq a_j$,应该按a升序排序($a_i$和$a_j$相等时无所谓)。

2.当$a_i=b_i$,$a_j=b_j$时,爱怎么排怎么排。

3.当$a_i>b_i$,$a_j>b_j$时,$b_i\geq b_j$,应该按b降序排序。

那么这三大组之间应该怎样排序呢?

1组和2组,1组在2组前肯定能保证满足条件。2组和3组,2组在3组前面肯定能保证满足条件。那么1组在前,2组在中,3组在后,是肯定能保证满足要求的。

我们令$d_i=\frac{a_i-b_i}{|a_i-b_i|}$,那么1组的d值为-1,2组为0,3组为1。

于是我们得到了最终的排序条件:先按d值排序;然后若d值小于等于0,按a升序排序(这里把2组归入1组);若d值大于0,则按b降序排序。 这样就可以满足传递性了。

这是完全正确的代码:

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{
    int x,y,d;
    bool operator <(node a) const
    {
        if (d!=a.d) return d<a.d;
        if (d<=0) return x<a.x;
        return y>a.y;
    }
}a[20005];
int t,n;
long long c[20005];
int main()
{
    cin>>t;
    for (int k=1;k<=t;k++)
    {
        cin>>n;
        for (int i=1;i<=n;i++) 
        {
            cin>>a[i].x>>a[i].y;
            if (a[i].x>a[i].y) a[i].d=1;
            else if (a[i].x<a[i].y) a[i].d=-1;
            else a[i].d=0;
        }
        sort(a+1,a+n+1);
        long long s=0;
        for (int i=1;i<=n;i++)
        {
            s+=a[i].x;
            c[i]=max(c[i-1],s)+a[i].y;
        }
        cout<<c[n]<<'\n';
    }
}

总结

这一道题是一道不错的题,美中不足的是,数据太弱了,以致于让错误的解法鱼目混珠。这一道题对得起省选/NOI-的难度评定。希望下次来看的时候,数据已经加强了,正确的解法已经深入人心了。

评论

  • EMT__Mashiro
    %%%
  • peroxide
    %%%
  • Sagume
    %%%
  • sky3141
    %%%
  • lx2005
    %%%
  • Segmentation_fault
    推了几天终于推出来了。。
  • Yygq_Master
    %%%
  • 机惨自动机
    %%%
  • WYH606iii
    %%%
  • taopinlin
    orz
作者: TA123 更新时间: 2018-07-26 12:34  在Ta的博客查看 举报    75  

做法

令$d_i = sgn(a_i - b_i)$

先按$d_i(-1,0,1)$顺序把大臣分为三组,在每一组内分别排序:

  1. $d_i=-1$,按$a_i$升序排序。
  2. $d_i=0$,以任意顺序排序。
  3. $d_i=1$,按$b_i$降序排序。

求出$c_n$并输出。

证明

偏序关系

令$P_{i,j}=\left \{ \begin{aligned} [d_i<d_j] & ,d_i != d_j \\ [a_i \le a_j] & ,d_i=d_j \le 0 \\ [b_i > b_j] & ,d_i=d_j=1 \end{aligned} \right.$

(即按上述做法重载$\le$)

因为$P_{i,j}$不过是多个排序的复合,所以它满足自反、反对称和传递性,是一个偏序关系,可以以$P_{i,j}$作为$\le$来排序。

接下来只需要证明若$P_{i,i+1}=1$,则交换$i$和$i+1$不会使答案更优即可。

何时更优

注意到$\forall 0 \le i < n,c_i \le c_{i+1}$,所以交换时我们只需要考虑后一项的大小关系,什么时候交换不会导致答案变优呢?(下面以$j=i+1$;$c$是$c_{i-1}$;$s=\sum_{k=1}^{i-1}a_k$)

$$\max ( \max (c,s + a_i) + b_i,s + a_i + a_j) + b_j$$ $$= \max \{ c , s + a_i , s + a_i - b_i + a_j \} + b_i + b_j$$ $$\le \max \{ c, s + a_j , s + a_j - b_j + a_i \} + b_i + b_j$$

化简:$\max (a_i, a_i - b_i + a_j ) \le \max (a_j,a_j - b_j + a_i)$

两边同时减去$a_i + a_j$:$\max (-a_j,-b_i) \le \max (-a_i,-b_j)$

乘以$-1$:$\min (a_j,b_i) \le \min (a_i,b_j)$

拆解成逻辑表达式: $$(a_i \le a_j \lor b_j \le a_j) \land (a_i \le b_i \lor b_j \le b_i)(*)$$

在此相遇

至此,我们只需要验证$P_{i,j}=1$时符合$( * )$式即可。

  1. $d_i = d_j \le 0$:$a_i \le a_j$,满足左边;$a_i \le b_i$,满足右边。
  2. $d_i = d_j =1$:$b_j < a_j$,满足左边;$b_j < b_i$,满足右边。
  3. $d_i < d_j$:$b_j \le a_j$,满足左边;$a_i \le b_i$,满足右边。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50000;
struct Secretary
{
    int a, b, d;
} sty[N + 5];
inline bool cmp(const Secretary &x, const Secretary &y)
{
    if (x.d != y.d)
        return x.d < y.d;
    if (x.d <= 0)
        return x.a < y.a;
    else
        return x.b > y.b;
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &sty[i].a, &sty[i].b);
            sty[i].d = sty[i].a - sty[i].b;
            if (sty[i].d)
                sty[i].d /= abs(sty[i].d);
        }
        sort(sty + 1, sty + n + 1, cmp);
        ll c = 0, s = 0;
        for (int i = 1; i <= n; ++i)
        {
            s += sty[i].a;
            c = max(c, s) + sty[i].b;
        }
        printf("%lld\n", c);
    }
}

评论

  • wjyyy
    前排看不懂
  • CYJian
    tql%%%
  • 可爱小纳尔
    orz
  • 天泽龟
    ORZ
  • ouuan
    题解区的LaTeX渲染貌似有点问题..可以在博客看
  • Nero_Claudius
    orzorz
  • ouuan
    还是提醒一下,本篇题解只讲了排序部分,其它部分就看其它题解好了
  • Irressey
    反正Orz就对了
  • wangzeyuanwangzeyuan
    orz
  • Itst天下第一
    orz!
作者: ouuan 更新时间: 2018-10-31 16:37  在Ta的博客查看 举报    60  

题目地址

相关文章

内容简介

  1. 详细说明直接比较 $\min(a_i,b_j)$ 和 $\min(a_j,b_i)$ 为什么是错的。

  2. 给出一(实际上是两)种无需 $d_i=sgn(a_i-b_i)$ 的做法。

  3. 给出一份判断一个比较方式是否是正解的代码。

所以,看懂本篇题解并不是解题所必要的,事实上本篇题解并没有讲如何推导出贪心式,这部分其它题解已经讲得很详细了。

但如果能看懂本篇题解的思想,并亲自推一遍,一定会有不小的收获。

本篇题解公式极多,等号极多,下标极多,难免手误,还请指出。

Part0

看本篇题解需要对Strict Weak Ordering有所了解,可以参考这篇博客

简单来说,$\rm STL$ 的任何比较函数(包括但不限于使用std::sortstd::lower_boundstd::priority_queue时重载的小于号),都需要满足以下四个条件:(用 $<$ 表示重载的运算符)

  1. $x\not<x$ (非自反性)
  2. 若 $x<y$,则 $y\not<x$ (非对称性)
  3. 若 $x<y,y<z$,则 $x<z$ (传递性)
  4. 若 $x\not<y,y\not<x,y\not<z,z\not<y$,则 $x\not<z,z\not<x$ (不可比性的传递性)

事实上可以由 $1$ 和 $3$ 推出 $2$ 。

Part1

这部分严格地证明了不能直接比较 $\min(a_i,b_j)$ 和 $\min(a_j,b_i)$

一、

为什么比较时不能加等号,即为什么不能是 $\min(a_i,b_j)\le \min(a_j,b_i)$。

因为如果加了等号,$\min(a_i,b_i)\le \min(a_i,b_i)$,不满足非自反性。

二、

为什么不加等号也是错的呢?因为有hack数据

2
7
6 3
1 1
7 3
1 1
1 6
1 1
6 10
7
6 10
1 1
6 3
1 1
7 3
1 1
1 6
26
26

这篇题解中提到了:

错误的根本原因就是,这个判断条件不满足传递性。

实际上这个判断条件满足传递性,但不满足不可比性的传递性。

满足传递性的证明:

命题:$\forall \begin{cases}\min(a_i,b_j)<\min(a_j,b_i)\\\min(a_j,b_k)<\min(a_k,b_j)\end{cases}$,有 $\min(a_i,b_k)<\min(a_k,b_i)$。

将上式拆解成逻辑式,即证:

$\forall \begin{cases}(a_i<a_j\lor b_j<a_j)\land(a_i<b_i\lor b_j<b_i)\\(a_j<a_k\lor b_k<a_k)\land(a_j<b_j\lor b_k<b_j)\end{cases}$,有 $(a_i<a_k\lor b_k<a_k)\land(a_i<b_i\lor b_k<b_i)$。

假设原命题不成立,即 $\exists\begin{cases}(a_i<a_j\lor b_j<a_j)\land(a_i<b_i\lor b_j<b_i)\quad(1)\\(a_j<a_k\lor b_k<a_k)\land(a_j<b_j\lor b_k<b_j)\quad(2)\\(a_i\ge a_k\land b_k\ge a_k)\lor(a_i\ge b_i\land b_k\ge b_i)\quad(3)\end{cases}$

分别讨论 $(3)$ 式成立的两种情况:

若 $a_i\ge a_k\land b_k\ge a_k$,由 $(2)$ 式得 $a_j<a_k$,进而推出 $a_j<a_i$,再由 $(1)$ 式得 $b_j<a_j$,再由 $(2)$ 式得到 $b_k<b_j$,所以 $b_k<b_j<a_j<a_k$,与 $b_k\ge a_k$ 矛盾,不成立。

若 $a_i\ge b_i\land b_k\ge b_i$,与上面类似,由 $(1)$ 式得 $b_j<b_i$,进而推出 $b_j<b_k$,再由 $(2)$ 式得到 $a_j<b_j$,再由 $(1)$ 式得到 $a_i<a_j$,所以 $a_i<a_j<b_j<b_i$,与 $a_i\ge b_i$ 矛盾,不成立。

综上所述,假设不成立。

所以,$P_{i,j}=\min(a_i,b_j)<\min(a_j,b_i)$ 具有传递性。

不具有不可比性的传递性的证明:

命题:$\forall \begin{cases}\min(a_i,b_j)=\min(a_j,b_i)\\\min(a_j,b_k)=\min(a_k,b_j)\end{cases}$,有 $\min(a_i,b_k)=\min(a_k,b_i)$。

很明显,当 $a_j=b_j$ 且都很小时存在反例,如:

$\begin{array}{c|c|c}&a&b\\i&3&5\\j&1&1\\k&2&7\end{array}$

$\begin{cases}\min(3,1)=\min(1,5)\\\min(1,7)=\min(2,1)\end{cases}$,但 $\min(3,7)\ne \min(2,5)$。

这样的反例还有很多,所以,$P_{i,j}=\min(a_i,b_j)<\min(a_j,b_i)$ 不具有不可比性的传递性。

三、

总结:$P_{i,j}=\min(a_i,b_j)<\min(a_j,b_i)$ 不满足Strict Weak Ordering的要求,不能作为std::sort的比较函数。

Part2

真的需要用 $d_i=sgn(a_i-b_i)$ 来分组比较吗?当然是不用的,而且个人认为像这篇题解这样做很不自然..起码我是想不到这种神奇的做法的QAQ.

上面写了一大堆公式,是不是已经有人已经跑路了..现在开始讲一些纯贪心内容。

比较相邻两项时,若 $\min(a_i,b_j)=\min(a_j,b_i)$ ,从全局来看,把 $a$ 更小的放前面是不会更差的。所以得到另一个排序方式:

$P^{'}_{i,j}=\begin{cases}a_i<a_j\quad(\min(a_i,b_j)=\min(a_j,b_i))\\\min(a_i,b_j)<\min(a_j,b_i)\quad(otherwise)\end{cases}$

讲完了短暂的贪心,又要开始证明了

满足非自反性:

$\min(a_i,b_i)=\min(a_i,b_i)$,$a_i\not <a_i$。

满足非对称性:

当 $\min(a_i,b_j)<\min(a_j,b_i)$ 时,$\min(a_j,b_i)\not <\min(a_i,b_j)$。

当 $\min(a_i,b_j)=\min(a_j,b_i),a_i<a_j$ 时,$\min(a_j,b_i)=\min(a_i,b_j),a_j\not <a_i$。

满足传递性和不可比性的传递性:

一开始我想像上面那样分类讨论做..然后差点就把这篇文章弃坑了..

后来才想起来我是OIer不是MOer

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

bool cmp(int x,int y);

int a[10],b[10];

int main()
{
    for (a[0]=1;a[0]<=6;++a[0])
    {
        for (b[0]=1;b[0]<=6;++b[0])
        {
            if (cmp(0,0))
            {
                printf("No irreflexivity:%d %d\n",a[0],b[0]);
            }
            for (a[1]=1;a[1]<=6;++a[1])
            {
                for (b[1]=1;b[1]<=6;++b[1])
                {
                    if (cmp(0,1)&&min(a[0],b[1])>min(a[1],b[0]))
                    {
                        printf("Not the best:%d %d %d %d\n",a[0],b[0],a[1],b[1]);
                    }
                    for (a[2]=1;a[2]<=6;++a[2])
                    {
                        for (b[2]=1;b[2]<=6;++b[2])
                        {
                            if (cmp(0,1)&&cmp(1,2)&&!cmp(0,2))
                            {
                                printf("No transitivity:%d %d %d %d %d %d\n",a[0],b[0],a[1],b[1],a[2],b[2]);
                            }
                            if (!cmp(0,1)&&!cmp(1,0)&&!cmp(1,2)&&!cmp(2,1)&&(cmp(0,2)||cmp(2,0)))
                            {
                                printf("No transitivity of incomparability:%d %d %d %d %d %d\n",a[0],b[0],a[1],b[1],a[2],b[2]);
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}

bool cmp(int x,int y)
{
    return min(a[x],b[y])==min(a[y],b[x])?a[x]<a[y]:min(a[x],b[y])<min(a[y],b[x]);
}

运行,什么都没发生??那就对了!

这说明 $P^{'}_{i,j}=\begin{cases}a_i<a_j\quad(\min(a_i,b_j)=\min(a_j,b_i))\\\min(a_i,b_j)<\min(a_j,b_i)\quad(otherwise)\end{cases}$ 既满足strict weak ordering,又保证排好序后替换邻项不会更优,是一个可以解决这道题目的排序方式。

事实上,更改上面给出的代码中的cmp,若没有任何输出即可作为本题的比较函数。

可以利用上面的代码快速验证:

  • $P_{i,j}=\min(a_i,b_j)<\min(a_j,b_i)$ 不具有不可比性的传递性。

  • $P^{''}_{i,j}=\begin{cases}b_i>b_j\quad(\min(a_i,b_j)=\min(a_j,b_i))\\\min(a_i,b_j)<\min(a_j,b_i)\quad(otherwise)\end{cases}$ 是这题另一个可行的比较方式。

  • $P^{'''}_{i,j}=\begin{cases}a_i>a_j\quad(\min(a_i,b_j)=\min(a_j,b_i))\\\min(a_i,b_j)<\min(a_j,b_i)\quad(otherwise)\end{cases}$ 不具有传递性。

评论

  • mlj2004
    tql!tql!tql!
  • RAYMOND_7
    orz
作者: 杨戬大师 更新时间: 2019-08-08 12:10  在Ta的博客查看 举报    7  

恕我直言,完成这道题,大体可以分为两个步骤:

1,找到正确的贪心策略,然后根据这个策略写出sort排序的bool函数,注意一定要定义一个结构体,再用sort排序一遍,这样我们就可以得到一个我们想要的让max最小的序列。

2,排序后贪心就完成了,接下来只需要按照题目所述的要求进行模拟。模拟完了,答案就出来了。

先来说说第一步,根据:

c[1]=a[1]+b[1];

c[i]=max(c[i-1],(a[1]+a[2]+...+a[i]))+b[i]。(1<i<=n)

可以看出,前后两个大臣,后面的肯定比前面的得到的钱多,所以题中所谓的“拿钱最多的大臣”不过是指站在最后的大臣。这是很简单就能看出来也是很重要的一步。然后,我们开始思考贪心的策略。

我们在做比较简单的贪心题的时候,每一步都是在都贪心,即找到最优方案。每一步贪,最后得到的便是最优的,这道题也一样:根据刚刚我们得到的结论,如果我们在每一次小小的排序中取最优解的话,那么排完序得到最后一个大臣的也便是最优解了。所以,我们先从两个大臣排序的情况入手:

c[2]=a[1]+b[2]+max(a[2],b[1]),我们再进行一下恒等变换

c[2]=(a[1]+a[2]+b[1]+b[2])-min(a[2],b[1]),排序一共有两种情况,这是第一种,1在2前面。

c[2]=(a[1]+a[2]+b[1]+b[2])-min(a[1],b[2]),这是第二种情况,2在1前面。

比较两种情况,发现区别就在min里面:如果a[1],a[2],b[1],b[2]四个数的最小值在a[1]或b[2]中,那么第一种情况的c[2]无疑比第二种情况的c[2]要小,排序要将1排在2前面。反之,若在a[2]或b[1]中,那么把2排到1前面就是更好的选择了。看一下这一部分的代码:

struct dachen
{
    int l,r;
}zz[20005];
bool master_cmp(dachen a, dachen b)
{
    if (a.l<=a.r&&a.l<=b.l||b.l<=a.l&&b.l<=b.r)
    {//若a.l或b.l中有可以碾压对方两组的
        if (a.l!=b.l)
            return a.l<b.l;
        return a.r>b.r;//若a.l与b.l相等就换一边
    }
    if (a.r!=b.r)//下面的意思同上一个if里的一样
        return a.r>b.r;
    return a.l<b.l;
}

刚刚,我们通过贪心完成了此题最难想的一步,接下来,只需要通过模拟推出答案,这便是第二步。这一步的模拟思维难度较刚刚说的贪心低多了,代码也很容易实现。我们只需要一次从1到n的循环,每一出来都求一下那个大臣的钱数,最后出来的最后一个大臣的钱数,就是答案了。

直接上代码:

#include <cstdio>
#include <algorithm>

using namespace std;

struct dachen
{
    int l,r;
}zz[20005];
bool master_cmp(dachen a, dachen b)
{
    if (a.l<=a.r&&a.l<=b.l||b.l<=a.l&&b.l<=b.r)
    {
        if (a.l!=b.l)
            return a.l<b.l;
        return a.r>b.r;
    }
    if (a.r!=b.r)
        return a.r>b.r;
    return a.l<b.l;
}
int main()
{
    int t,n,i;
    long long left,ans;//一定要注意long long!
    scanf("%d",&t);
    while (t--)
    {
        left=0;
        ans=0;
        scanf("%d",&n);
        for (i=1;i<=n;i++)
            scanf("%d%d",&zz[i].l,&zz[i].r);
        sort(zz+1,zz+n+1,master_cmp);
        for (i=1;i<=n;i++)
        {
            left+=zz[i].l;//left表示到现在为止前面所有大臣的左手的和
            if (ans<left)//按要求求每个人的钱数
                ans=left+zz[i].r;
            else
                ans+=zz[i].r;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

这道题现在看来,就是一个贪心的排序加模拟。难度集中在如何找到好的排序方法,根据贪心找到方法后,题目便变容易了。

评论

  • love_cxk
    挂掉的markdown在这里:https://cdn.luogu.com.cn/upload/image_hosting/ls53x27t.png
  • love_cxk
    https://cdn.luogu.com.cn/upload/ image_hosting/ls53x27t.png
  • 小枪
    大佬666
作者: wlj_55  更新时间: 2019-10-16 15:12  在Ta的博客查看 举报    4  

前言

此题的关键就是证明对于两位大臣$i,j$,如果$min(a_i,b_j)\le min(a_j,b_i)$,那么我们将$i$放在前面更优。

由于笔者认为大部分题解对于上述结论的证明都是大同小异或是一带而过,故此处给出上述结论的一种不同的证明方式,后续处理其余题解已经讲得很清楚,故此处不再赘述。

正题

传送门

解析:题目要求的是这样一个式子中$c[i]$的最大值的最小值: 由于$a_i,b_i$均为正数,所以$c_i$一定是递增的,故我们要求的即为$c_n$的最小值。

我们有一个结论:对于两位大臣$(a_i,b_i),(a_j,b_j)$,如果$min(a_i,b_j)\le min(a_j,b_i)$,那么我们将$(a_i,b_i)$放在前面更优,证明如下:

$$c_1=a_1+b_1$$ $$c_2=max(c_1,a_1+a_2)+b_1=max(a_1+b_1,a_1+a_2)+b_2$$ $$c_2=max(a_1+b_1+b_2,a_1+a_2+b_2)$$ $$c_3=max(c_2,a_1+a_2+a_3)+b_3$$ $$c_3=max(a_1+b_1+b_2,a_1+a_2+b_2,a_1+a_2+a_3)+b_3$$ $$c_3=max(a_1+b_1+b_2+b_3,a_1+a_2+b_2+b_3,a_1+a_2+a_3+b_3)$$ 综上,我们可以发现一个规律:

我们记$S_n(k)$为$\sum_{i=1}^ka_i+\sum_{i=k}^nb_i$

那么$c_i=max(S_i(1),S_i(2),S_i(3),...,S_i(i))$

但这只是我们找出来的规律,下面给出严谨证明:

我们考虑用一个$2*n$的矩阵来表示我们的序列$(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$

以$c_3$为例,我们来画出这些走法,它们分别对应所有的$S_3$:

所以$c_n$在我们的矩阵里表示从$a_1$到$b_n$的$n$条路径中$n+1$个数字和的最大值。

我们用数学归纳法证明$c_i=max(S_i(1),S_i(2),S_i(3),...,S_i(i))$:

当$n=1$时,$c_1=max(S_1(1))$,显然成立。

假设当$n=k(k\ge1)$时,命题成立,即$c_k=max(S_k(1),S_k(2),S_k(3),...,S_k(k))$

那么当$n=k+1$时,

$$c_{k+1}=max(c_k,a_1+a_2+...+a_{k+1})+b_{k+1}$$ 将$b_{k+1}$带入$max$中 $$c_{k+1}=max(c_k+b_{k+1},a_1+a_2+...+a_{k+1}+b_{k+1})$$ 合并后面的项 $$c_{k+1}=max(c_k+b_{k+1},S_{k+1}(k+1))$$ 将$c_k$拆开 $$c_{k+1}=max(S_k(1)+b_{k+1},S_k(2)+b_{k+1},...,S_k(k)+b_{k+1},S_{k+1}(k+1))$$ 按照$S$的定义合并所有项 $$c_{k+1}=max(S_{k+1}(1),S_{k+1}(2),...,S_{k+1}(k+1))$$ 原命题得证。

下一步,我们来证明如果$min(a_i,b_j)\le min(a_j,b_i)$,那么我们将$(a_i,b_i)$放在前面更优。

考虑上文提到的矩阵,我们对于一个矩阵 $$ \begin{bmatrix} a_1 & a_2 &a_3 &...&a_n\\ b_1 & b_2&b_3&...&b_n \end{bmatrix} $$ 我们如果调换两人的顺序,也就是调换矩阵中两列的顺序。

我们假设调换第$k$列和第$k+1$列,我们得到一个新矩阵

$$ \begin{bmatrix} a_1' & a_2' &a_3' &...&a_n'\\ b_1' & b_2'&b_3'&...&b_n' \end{bmatrix} $$ 其中 $$ \begin{bmatrix} a_i \\ b_i \end{bmatrix}=\begin{bmatrix} a_i' \\ b_i' \end{bmatrix}\quad(1\le i\le n,i≠k,i≠k+1) $$ $$ \begin{bmatrix} a_k \\ bk \end{bmatrix}=\begin{bmatrix} a{k+1}' \\ b{k+1}' \end{bmatrix}\quad $$ $$ \begin{bmatrix} a{k+1} \\ b{k+1} \end{bmatrix}=\begin{bmatrix} a{k}' \\ b_{k}' \end{bmatrix}\quad $$ 我们记$S_n'(k)$为$\sum_{i=1}^ka_i'+\sum_{i=k}^nb_i',c'_n=max(S_n'(1),S_n'(2),...,S_n'(n))$

我们设$\sigma=S_n(k-1)=S_n'(k-1)=\sum_{i=1}^{k-1}a_i+\sum_{i=k+2}^{n}b_i=\sum_{i=1}^{k-1}a_i'+\sum_{i=k+2}^{n}b_i'$,那么我们有:

$$S_n(k)=\sigma+a_k+b_k+b_{k+1}$$ $$S_n(k+1)=\sigma+a_k+a_{k+1}+b_{k+1}$$ $$S_n'(k)=\sigma+a_k'+b_k'+b_{k+1}'=\sigma+a_{k+1}+b_{k+1}+b_k$$ $$S_n'(k+1)=\sigma+a_k'+a_{k+1}'+b_{k+1}'=\sigma+a_{k+1}+a_k+b_k$$ 记$m=min(a_k,a_{k+1},b_k,b_{k+1}),M=max(S_n(k),S_n(k+1),S_n'(k),S_n'(k+1))$

我们分别讨论$m$的取值,

当$m=a_k$时,依照上文推出的$S,S'$的表达式,$M=S_n'(k)$,所以$max(S'_n(k),S_n'(k+1))\ge max(S_n(k),S_n(k+1))$,即$c_n'\ge c_n$

其余三种情况同理。

最后我们得出当$m=a_k$或$b_{k+1}$时,$c_n\le c_n'$,所以不应交换。

当$m=a_{k+1}$或$b_k$时,$c_n\ge c_n'$,此时应交换$k$与$k+1$两列。

证毕。

 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。