P2123 皇后游戏 题解


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

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

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

评论

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

洛谷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
    推了几天终于推出来了。。
  • 雄英天下第一
    %%%
  • 机惨自动机
    %%%
  • WYH606iii
    %%%
  • taopinlin
    orz
作者: TA123 更新时间: 2018-07-26 12:34  在Ta的博客查看 举报    50  

做法

令$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
  • 嘻嘻嘻嘻嘻
    orz!
作者: ouuan 更新时间: 2018-10-31 16:37  在Ta的博客查看 举报    39  

题目地址

内容简介

  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_j$。

满足非对称性:

当 $\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}$ 不具有传递性。

评论

  • Clight_Lee
    还没有评论
  • ouuan
    这个做法和 TA123 的题解本质相同,证明可以看他的题解,就是交换邻项不会更优 & 满足严格弱序要求。
作者: xmh060606 更新时间: 2019-04-19 15:14  在Ta的博客查看 举报    4  

看了各位大佬的题解,发现大多数都是用

min(a i ,b j )≤min(a j ,b i)

进行排序的

但是在参考了 一本叫做“信息学奥赛一本通·提高篇”的书 以后,发现了有一个东西叫“流水调度问题”,我们发现,A机器显然在不停的工作是最优的,要让A、B的总时间最短,就是要让B机器的空闲时间最短 而最终时间的求法恰好是题目中的式子(在上一件产品在B机器加工完,并且当前产品在A机器上加工完的时候,把当前产品放到B机器上加工)

怎样让B的空闲时间最小呢?显然,先生产a<b的产品,再生产a>b的产品是可以减少“A机器工作时,B机器没有活干”的情况

我们可以意会一下,我们要尽量地让B机器跟不上A机器的速度,好减少B机器的空闲时间,而且要避免A机器生产一个加工时间很长的产品时,B机器没有“存货”了

所以我们先生产a小b大的零件,多搞一些“存货”,减少B机器的空闲时间,排个序就行了。

但是证明这一块还无法给出绝对的证明,不知道有没有大佬能够在评论里说一下......

ac代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20010;
int T,n,cnt1,cnt2,c[N];
struct NODE{
int x,y;
} t[N],s1[N],s2[N];
inline bool cmp1(NODE a,NODE b){
return a.x<b.x;
}
inline bool cmp2(NODE a,NODE b){
return a.y>b.y;
}
undef int
int main()
define int long long
{
cin>>T;
while(T--){
    cin>>n;
    cnt1=cnt2=0;
    for(int i=1;i<=n;++i){
        cin>>&t[i].x>>&t[i].y;
        if(t[i].x<=t[i].y) s1[++cnt1]=t[i];
        else s2[++cnt2]=t[i];
    }
    sort(s1+1,s1+1+cnt1,cmp1);
    sort(s2+1,s2+1+cnt2,cmp2);
    for(int i=1;i<=cnt1;i++)
        t[i]=s1[i];
    for(int i=1;i<=cnt2;i++)
        t[cnt1+i]=s2[i];
    c[1]=t[1].x+t[1].y;
    int sum=t[1].x;
    for(int i=2;i<=n;i++){
        sum+=t[i].x;
        c[i]=max(c[i-1],sum)+t[i].y;
    }
    cout<<c[n]<<endl;
}
return 0;
}

评论

  • Mathison
    %%%
  • 三金Elsa
    zici
作者: lwz2002 更新时间: 2018-09-03 17:31  在Ta的博客查看 举报    4  

我一开始做这道题也是按照min(ai,bj)<=min(aj,bi)公式排序,而在看题解后我却发现了这个做法竟然不对(QAQ),而楼下的dalao的排序方式我看完之后一直不理解为什么这样排序还满足min(ai,bj)<=min(aj,bi)(可能是因为我太菜了),经过我漫长的思索后,终于理解了那样排序的精妙之处

我写这篇题解是给像我这样的蒟蒻一个更容易的理解

建议把我的题解和之前那几位dalao的题解结合看,毕竟我没给公式证明

(如果您太强,可以直接忽略掉我这篇题解QAQ)

思路

通过相邻交换法可得到

min(ai,bj)<=min(aj,bi)

这个简单而又精妙的公式,既然前面的dalao给出了证明,我这里就直接忽略了(逃

我就直接从楼下dalao的排序出发了

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];

把min(ai,bj)<=min(aj,bi)记为①式;

d表示的是a[i].x与a[i].y的大小,若x>y,则把d赋成1,x==y时d=0,x<y时d=-1

因为排序的第一步是比较d的值,我来解释一下(其实我一开始没看懂QAQ)

可以举个例子:若d不相等,设ai<bi,aj>bj,此时d<a.d

若ai<bj,则ai一定是这四个值中的最小值,所以min(ai,bj)就等于ai,又因为ai为最小值,所以①式成立

若ai>bj,则bj一定是这四个值中的最小值,所以min(ai,bj)就等于bj,又因为bj为最小值,所以①式成立

所以这个排序看似没有按①式排序,实则却巧妙穿插,所以楼下dalao太强了%%%

以下是我的代码

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

using namespace std;
struct node
{
    int l;
    int r;
    int xuanxue;   //由于一开始没看懂dalao的代码,所以命名为xuanxueQAQ
}a[20010];
int n,t;
long long c[20010],f[20010];
int cmp(node a,node b)
{
    if(a.xuanxue!=b.xuanxue) return a.xuanxue<b.xuanxue;
    if(a.xuanxue<=0&&b.xuanxue<=0) return a.l<b.l;
    return a.r>b.r;
}
int main()
{
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
//      memset(c,0,sizeof c);
//      memset(f,0,sizeof f);
        int n;
        scanf("%d",&n);
        for(int j=1;j<=n;j++)
        {
            scanf("%d%d",&a[j].l,&a[j].r);
            if(a[j].l-a[j].r<0) a[j].xuanxue=-1;
            else if(a[j].l-a[j].r>0) a[j].xuanxue=1;
            else a[j].xuanxue=0;
        }
        sort(a+1,a+n+1,cmp);
        c[1]=a[1].l+a[1].r;
        f[1]=a[1].l;
        for(int j=2;j<=n;j++)
        {
            f[j]=a[j].l+f[j-1];
            c[j]=max(c[j-1],f[j])+a[j].r;
        }
        printf("%lld\n",c[n]);
    }
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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