[蓝桥杯青少年组国赛 2025] 第四题

Luogu
IDLGB4399
Time1000ms
Memory512MB
DifficultyP3
贪心单调队列2025排序蓝桥杯青少年组
给定 $n$ 个闭区间 $[l_i, r_i]$。你需要在数轴上选择一个**整数点**的集合 $P = \{p_1, p_2, \dots, p_k\}$,满足以下两个条件: 1. 对于每一个给定的区间 $[l_i, r_i]$,都**至少存在**一个你选择的点 $p_j \in P$,使得 $l_i \le p_j \le r_i$。 2. 定义一个选择 $P$ 的方案的总成本为 $\sum \limits_{j=1}^{k} p_j$。总成本需要达到最小。 你需要计算出这个最小的总成本。 ## Input 第一行包含一个整数 $n$,表示区间的数量。 接下来 $n$ 行,每行包含两个整数 $l_i$ 和 $r_i$,描述一个区间的左右端点。 ## Output 输出一个整数,表示满足条件的最小总成本。 [samples] ## Background 洛谷的试题为民间回忆版,仅保证题意相同。试题呈现形式、样例、数据范围可能存在差异。 ## Note ### 样例解释 选择点 $1,6$ 可以获得最小的总成本,答案为 $1+6=7$。 ### 数据范围与约定 对于 100% 的数据,满足 $1 \leq n \leq 10^5$,$1 \leq l_i \leq r_i \leq 10^9$;
Samples
Input #1
3
1 5
3 7
6 8
Output #1
7
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯青少年组国赛 2025] 第四题",
    "description": {
      "content": "给定 $n$ 个闭区间 $[l_i, r_i]$。你需要在数轴上选择一个**整数点**的集合 $P = \\{p_1, p_2, \\dots, p_k\\}$,满足以下两个条件: 1. 对于每一个给定的区间 $[l_i, r_i]$,都**至少存在**一个你选择的点 $p_j \\in P$,使得 $l_i \\le p_j \\le r_i$。 2. 定义一个选择 $P$ 的方案的总成本为 $\\sum ",
      "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": "LGB4399"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$ 个闭区间 $[l_i, r_i]$。你需要在数轴上选择一个**整数点**的集合 $P = \\{p_1, p_2, \\dots, p_k\\}$,满足以下两个条件:\n\n1. 对于每一个给定的区间 $[l_i, r_i]$,都**至少存在**一个你选择的点 $p_j \\in P$,使得 $l_i \\le p_j \\le r_i$。\n2. 定义一个选择 $P$ 的方案的总成本为 $\\sum ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments