B. Optimal Point on a Line

Codeforces

IDCF710B

Time1000ms

Memory256MB

Difficulty—

brute forcesortings

English · Original

Chinese · Translation

Formal · Original

You are given _n_ points on a line with their coordinates _x__i_. Find the point _x_ so the sum of distances to the given points is minimal. ## Input The first line contains integer _n_ (1 ≤ _n_ ≤ 3·105) — the number of points on the line. The second line contains _n_ integers _x__i_ ( - 109 ≤ _x__i_ ≤ 109) — the coordinates of the given _n_ points. ## Output Print the only integer _x_ — the position of the optimal point on the line. If there are several optimal points print the position of the leftmost one. It is guaranteed that the answer is always the integer. [samples]

给定一条直线上 #cf_span[n] 个点的坐标 #cf_span[xi]，请找到一个点 #cf_span[x]，使得它到所有给定点的距离之和最小。第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105]) —— 直线上点的个数。第二行包含 #cf_span[n] 个整数 #cf_span[xi] (#cf_span[ - 109 ≤ xi ≤ 109]) —— 给定的 #cf_span[n] 个点的坐标。请输出唯一的整数 #cf_span[x] —— 直线上最优点的位置。如果有多个最优点，请输出最左边的那个。题目保证答案一定是整数。 ## Input 第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105]) —— 直线上点的个数。第二行包含 #cf_span[n] 个整数 #cf_span[xi] (#cf_span[ - 109 ≤ xi ≤ 109]) —— 给定的 #cf_span[n] 个点的坐标。 ## Output 请输出唯一的整数 #cf_span[x] —— 直线上最优点的位置。如果有多个最优点，请输出最左边的那个。题目保证答案一定是整数。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of points. Let $ X = (x_1, x_2, \dots, x_n) $ be a sequence of real numbers representing the coordinates of the points, sorted such that $ x_1 \leq x_2 \leq \dots \leq x_n $. **Constraints** 1. $ 1 \leq n \leq 3 \cdot 10^5 $ 2. $ -10^9 \leq x_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the integer $ x \in \mathbb{Z} $ that minimizes the sum of absolute distances: $$ x = \arg\min_{z \in \mathbb{R}} \sum_{i=1}^n |z - x_i| $$ If multiple minimizers exist, choose the leftmost one. It is guaranteed that the minimizer is an integer, and in this case, $ x = x_{\lceil n/2 \rceil} $.

Samples

Input #1

4
1 2 3 4

Output #1

API Response (JSON)

{
  "problem": {
    "name": "B. Optimal Point on a Line",
    "description": {
      "content": "You are given _n_ points on a line with their coordinates _x__i_. Find the point _x_ so the sum of distances to the given points is minimal.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF710B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given _n_ points on a line with their coordinates _x__i_. Find the point _x_ so the sum of distances to the given points is minimal.\n\n## Input\n\nThe first line contains integer _n_ (1 ≤ _n_ ≤ 3...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一条直线上 #cf_span[n] 个点的坐标 #cf_span[xi]，请找到一个点 #cf_span[x]，使得它到所有给定点的距离之和最小。\n\n第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105]) —— 直线上点的个数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[xi] (#cf_span[ - 109 ≤ xi ≤ 109])...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of points.  \nLet $ X = (x_1, x_2, \\dots, x_n) $ be a sequence of real numbers representing the coordinates of the points, sorted such that $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments