P3933 Chtholly Nota Seniorious

    • 233通过
    • 1.1K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 二分答案 向量 贪心 O2优化 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms-3000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    经查,本题是原题,非常抱歉。

    大样例下发链接: https://pan.baidu.com/s/1nuVpRS1 密码: sfxg

    こんなにも、たくさんの幸せをあの人に分けてもらった

    だから、きっと

    今の、私は

    谁が何と言おうと

    世界一、幸せな女の子だ

    题目描述

    ——“假如……我是说假如喔。

    万一我再过五天就会死,你能不能对我温柔一点?”

    巨大的六号兽五天后将袭击浮游大陆。

    无数次计算得到的残酷数据表明,只有圣剑瑟尼欧尼斯的适格精灵——珂朵莉·诺塔·瑟尼欧尼斯(Chtholly Nota Seniorious)开启妖精乡之门,才可以以生命为代价守住浮游岛。

    “至少,我也希望自己不用消失,也想让别人记住。我也想留下羁绊啊。”

    留给妖精少女珂朵莉的时间似乎已经不多了。

    年轻的二等技官,妖精仓库的管理员,世界上最后一个人类——威廉·克梅,数百年前曾经是一名准勇者,掌握着成为一名勇者所需要的所有知识。

    大战在即,调整圣剑的状态成为了一项重要的任务。

    瑟尼欧里斯(セニオリス)
    圣剑的其中之一,在现存的遗迹兵装中,拥有最强大的力量。
    拥有非常特殊的资质,只有极少一部分的人才能使用。
    由四十一个护符组成。能将所有事物包含不死者都回归「死亡」。

    威廉需要调整圣剑的状态,因此他将瑟尼欧尼斯拆分护符,组成了一个 $n$ 行 $m$ 列的矩阵。

    每一个护符都有自己的魔力值。现在为了测试圣剑,你需要将这些护符分成 A,B两部分。

    要求如下:

    1. 圣剑的所有护符,恰好都属于两部分中的一部分。

    2. 每个部分内部的方块之间,可以通过上下左右相互到达,而且每个内部的方块之间互相到达,最多允许拐一次弯。

    例如

    AAAAA  AAAAA  AAAAA
    AABAA  BaAAA  AAABB
    ABBBA  BBAAA  AAABB
    AABAA  BaAAA  ABBBB
    AAAAA  AAAAA  BBBBB
    
      (1)     (2)     (3)      

    其中(1)(2)是不允许的分法,(3)是允许的分法。在(2)中,a属于A区域,这两个a元素之间互相到达,没有办法最多只拐一次弯。

    现在要问,所有合法的分法中,A区域的极差与B区域的极差 中间较大的一个的 最小值 是多少?

    好心而可爱的在一旁默默观察奈芙莲悄悄地告诉你,极差就是区域内最大值减去最小值。

    夜晚的风吹拂着,68号岛上的景色竟与地上的森林无异。转念又想,黄金妖精本身就是与森林之中出现,成长,消亡的神秘存在啊。

    时间不早了,早上训练中落败的珂朵莉即将回来了。您要尽快和威廉一起调整好圣剑,千万不能迟哟。

    输入输出格式

    输入格式:

    第一行两个自然数 $n,m$

    接下来 $n$ 行,每行 $m$ 个自然数 $A_{i,j}$ 表示权值

    输出格式:

    一个整数表示答案。

    输入输出样例

    输入样例#1: 复制
    4 4
    1 12 6 11
    11 4 2 14
    10 1 9 20
    4 17 13 10
    输出样例#1: 复制
    11

    说明

    样例解释

    1  12 6        11
    11 4  2        14
    10 1  9        20
    4        17 13 10

    分法不唯一,如图是一种合法的分法。左边部分极差12-1=11,右边一块极差20-10=10,所以答案取这两个中较大者11。没有别的分法,可以使答案更小。

    数据范围与约定

    测试点   n     m    
    #1-2 $\le 10$ $\le 10$
    #3-4 1 $\le 2000$
    #5-7 $\le 200$ $\le 200$
    #8-10 $\le 2000$ $\le 2000$

    对于所有的权值 $1\le A_{i,j} \le 10^9$

    《末日时在做什么?有没有空?可以来拯救吗?》

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。