[蓝桥杯 2017 国 A] 区间移位

Luogu

IDLGP8660

Time1000ms

Memory128MB

DifficultyP5

贪心2017二分排序蓝桥杯国赛

数轴上有 $n$ 个闭区间：$D_1, \cdots ,D_n$。其中区间 $D_i$ 用一对整数 $[a_i,b_i]$ 来描述，满足 $a_i<b_i$。已知这些区间的长度之和至少有 $10000$。所以，通过适当的移动这些区间，你总可以使得他们的“并”覆盖 $[0,10000]$ ——也就是说 $[0,10000]$ 这个区间内的每一个点都落于至少一个区间内。你希望找一个移动方法，使得位移差最大的那个区间的位移量最小。具体来说，假设你将 $D_i$ 移动到 $[a_i+c_i,b_i+c_i]$ 这个位置。你希望使得 $\max\limits_{i=1}^n\{|c_i|\}$ 最小。 ## Input 输入的第一行包含一个整数 $n$，表示区间的数量。接下来有 $n$ 行，每行 $2$ 个整数 $a_i,b_i$，以一个空格分开，表示区间 $[a_i,b_i]$。保证区间的长度之和至少是 $10000$。 ## Output 输出一个数字，表示答案。如果答案是整数，只输出整数部分。如果答案不是整数，输出时四舍五入保留一位小数。 [samples] ## Note **【样例解释】** 样例 1：第一个区间往左移动 $10$；第二个区间往右移动 $20$。样例 2：第 $2$ 个区间往右移 $0.5$；第 $3$ 个区间往左移 $0.5$ 即可。 **【数据范围】** 对于 $30\%$ 的评测用例，$1 \le n \le 10$；对于 $100\%$ 的评测用例，$1 \le n \le 10000$，$0 \le a_i<b_i \le 10000$。

Samples

Input #1

2
10 5010
4980 9980

Output #1

Input #2

Output #2

0.5

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2017 国 A] 区间移位",
    "description": {
      "content": "数轴上有 $n$ 个闭区间：$D_1, \\cdots ,D_n$。 其中区间 $D_i$ 用一对整数 $[a_i,b_i]$ 来描述，满足 $a_i<b_i$。 已知这些区间的长度之和至少有 $10000$。 所以，通过适当的移动这些区间，你总可以使得他们的“并”覆盖 $[0,10000]$ ——也就是说 $[0,10000]$ 这个区间内的每一个点都落于至少一个区间内。 你希望找一个移动",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8660"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "数轴上有 $n$ 个闭区间：$D_1, \\cdots ,D_n$。\n\n其中区间 $D_i$ 用一对整数 $[a_i,b_i]$ 来描述，满足 $a_i<b_i$。\n\n已知这些区间的长度之和至少有 $10000$。\n\n所以，通过适当的移动这些区间，你总可以使得他们的“并”覆盖 $[0,10000]$ ——也就是说 $[0,10000]$ 这个区间内的每一个点都落于至少一个区间内。\n\n你希望找一个移动...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments