I. Photo Processing

Codeforces

IDCF883I

Time3000ms

Memory256MB

Difficulty—

binary searchdp

English · Original

Chinese · Translation

Formal · Original

Evlampiy has found one more cool application to process photos. However the application has certain limitations. Each photo _i_ has a contrast _v__i_. In order for the processing to be truly of high quality, the application must receive at least _k_ photos with contrasts which differ as little as possible. Evlampiy already knows the contrast _v__i_ for each of his _n_ photos. Now he wants to split the photos into groups, so that each group contains at least _k_ photos. As a result, each photo must belong to exactly one group. He considers a processing time of the _j_\-th group to be the difference between the maximum and minimum values of _v__i_ in the group. Because of multithreading the processing time of a division into groups is the maximum processing time among all groups. Split _n_ photos into groups in a such way that the processing time of the division is the minimum possible, i.e. that the the maximum processing time over all groups as least as possible. ## Input The first line contains two integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 3·105) — number of photos and minimum size of a group. The second line contains _n_ integers _v_1, _v_2, ..., _v__n_ (1 ≤ _v__i_ ≤ 109), where _v__i_ is the contrast of the _i_\-th photo. ## Output Print the minimal processing time of the division into groups. [samples] ## Note In the first example the photos should be split into 2 groups: \[40, 50\] and \[110, 120, 130\]. The processing time of the first group is 10, and the processing time of the second group is 20. Maximum among 10 and 20 is 20. It is impossible to split the photos into groups in a such way that the processing time of division is less than 20. In the second example the photos should be split into four groups, each containing one photo. So the minimal possible processing time of a division is 0.

Evlampiy 找到了另一个用于处理照片的酷炫应用程序，但该应用程序有一些限制。每张照片 #cf_span[i] 具有对比度 #cf_span[vi]。为了实现高质量的处理，应用程序必须接收至少 #cf_span[k] 张对比度尽可能接近的照片。 Evlampiy 已经知道了他拥有的 #cf_span[n] 张照片的对比度 #cf_span[vi]。现在他希望将这些照片分成若干组，使得每组至少包含 #cf_span[k] 张照片。最终，每张照片必须恰好属于一个组。他将第 #cf_span[j] 组的处理时间定义为该组中 #cf_span[vi] 的最大值与最小值之差。由于多线程处理，整个分组方案的处理时间是所有组中处理时间的最大值。请将 #cf_span[n] 张照片分成若干组，使得整个分组方案的处理时间最小化，即所有组中最大处理时间尽可能小。第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ k ≤ n ≤ 3·105]) —— 照片数量和每组的最小大小。第二行包含 #cf_span[n] 个整数 #cf_span[v1, v2, ..., vn] (#cf_span[1 ≤ vi ≤ 109])，其中 #cf_span[vi] 是第 #cf_span[i] 张照片的对比度。请输出分组方案的最小处理时间。在第一个示例中，照片应被分为两组：#cf_span[[40, 50]] 和 #cf_span[[110, 120, 130]]。第一组的处理时间为 #cf_span[10]，第二组的处理时间为 #cf_span[20]。#cf_span[10] 和 #cf_span[20] 中的最大值为 #cf_span[20]。不可能将照片分成处理时间小于 #cf_span[20] 的组。在第二个示例中，照片应被分为四个组，每组包含一张照片。因此，分组方案的最小可能处理时间为 #cf_span[0]。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ k ≤ n ≤ 3·105]) —— 照片数量和每组的最小大小。第二行包含 #cf_span[n] 个整数 #cf_span[v1, v2, ..., vn] (#cf_span[1 ≤ vi ≤ 109])，其中 #cf_span[vi] 是第 #cf_span[i] 张照片的对比度。 ## Output 请输出分组方案的最小处理时间。 [samples] ## Note 在第一个示例中，照片应被分为两组：#cf_span[[40, 50]] 和 #cf_span[[110, 120, 130]]。第一组的处理时间为 #cf_span[10]，第二组的处理时间为 #cf_span[20]。#cf_span[10] 和 #cf_span[20] 中的最大值为 #cf_span[20]。不可能将照片分成处理时间小于 #cf_span[20] 的组。在第二个示例中，照片应被分为四个组，每组包含一张照片。因此，分组方案的最小可能处理时间为 #cf_span[0]。

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 3 \cdot 10^5 $. Let $ V = (v_1, v_2, \dots, v_n) $ be a sequence of integers with $ 1 \leq v_i \leq 10^9 $. **Constraints** 1. Each group must contain at least $ k $ photos. 2. Every photo belongs to exactly one group. **Objective** Partition $ V $ into disjoint groups $ G_1, G_2, \dots, G_m $ such that $ |G_j| \geq k $ for all $ j $, and minimize: $$ \max_{j} \left( \max_{v \in G_j} v - \min_{v \in G_j} v \right) $$ Assume $ V $ is sorted: $ v_1 \leq v_2 \leq \dots \leq v_n $.

Samples

Input #1

5 2
50 110 130 40 120

Output #1

Input #2

4 1
2 3 4 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "I. Photo Processing",
    "description": {
      "content": "Evlampiy has found one more cool application to process photos. However the application has certain limitations. Each photo _i_ has a contrast _v__i_. In order for the processing to be truly of high ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF883I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Evlampiy has found one more cool application to process photos. However the application has certain limitations.\n\nEach photo _i_ has a contrast _v__i_. In order for the processing to be truly of high ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Evlampiy 找到了另一个用于处理照片的酷炫应用程序，但该应用程序有一些限制。\n\n每张照片 #cf_span[i] 具有对比度 #cf_span[vi]。为了实现高质量的处理，应用程序必须接收至少 #cf_span[k] 张对比度尽可能接近的照片。\n\nEvlampiy 已经知道了他拥有的 #cf_span[n] 张照片的对比度 #cf_span[vi]。现在他希望将这些照片分成若干组，使得每组...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 3 \\cdot 10^5 $.  \nLet $ V = (v_1, v_2, \\dots, v_n) $ be a sequence of integers with $ 1 \\leq v_i \\leq 10^9 $.\n\n**Constraints...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments