「MYOI-R3」极差

Luogu

IDLGP10444

Time1000ms

Memory512MB

DifficultyP3

贪心二分洛谷原创O2优化洛谷月赛双指针 two-pointerAd-hoc

对于一个序列 $c$ ，定义 $c$ 的极差为 $c$ 中最大值与最小值之差。现在给定一个长度为 $n$ 的序列 $a$，问是否能将其分成至少两个长度大于 $1$ 的子序列，使得每个子序列的极差都相等（注意，所有元素都必须分配且每个元素仅能分配到一个子序列中）。 ## Input **本题包含多组数据**。第一行两个整数 $T,id$，表示数据组数和子任务编号。对于每组数据，第一行一个正整数 $n$，表示数组长度。第二行 $n$ 个整数表示序列 $a$。 ## Output 对于每组数据，输出一行一个字符串 `Yes` 或 `No`。 [samples] ## Note ### 样例 $\small\text{1}$ 解释样例符合子任务 1 的约束，$id=1$。询问一：可以证明，没有任何方案满足条件。询问二：合法分配的一种子序列集合如下： - $\{1,9\}$。 - $\{1,9\}$。 - $\{8,1,0\}$。答案不唯一。 ### 数据规模与约定 **本题采用捆绑测试**。 - Subtask 1（20 points）：$4\le \sum n\le 20,a_i\ge 0$。 - Subtask 2（20 points）：$4\le \sum n\le 100,a_i\ge 0$。 - Subtask 3（20 points）：$4\le \sum n\le 10^3,a_i\ge 0$。 - Subtask 4（10 points）：$a$ 数组中元素相等。 - Subtask 5（30 points）：无特殊限制。对于 $100\%$ 的数据，$4\le \sum n\le 10^6,0\le |a_i|\le 10^9,1\le T\le 300$。

Samples

Input #1

2 1
6
1 1 4 5 1 4
7
1 9 1 9 8 1 0

Output #1

No
Yes

API Response (JSON)

{
  "problem": {
    "name": "「MYOI-R3」极差",
    "description": {
      "content": "对于一个序列 $c$ ，定义 $c$ 的极差为 $c$ 中最大值与最小值之差。现在给定一个长度为 $n$ 的序列 $a$，问是否能将其分成至少两个长度大于 $1$ 的子序列，使得每个子序列的极差都相等（注意，所有元素都必须分配且每个元素仅能分配到一个子序列中）。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10444"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对于一个序列 $c$ ，定义 $c$ 的极差为 $c$ 中最大值与最小值之差。现在给定一个长度为 $n$ 的序列 $a$，问是否能将其分成至少两个长度大于 $1$ 的子序列，使得每个子序列的极差都相等（注意，所有元素都必须分配且每个元素仅能分配到一个子序列中）。\n\n## Input\n\n**本题包含多组数据**。\n\n第一行两个整数 $T,id$，表示数据组数和子任务编号。\n\n对于每组数据，\n\n第一行...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments