[THUSC 2019] 紧急决策

Luogu

IDLGP10341

Time1000ms

Memory512MB

DifficultyP3

2019THUSC

在一片海岸上，有 $n$ 个灯塔，从 $1$ 到 $n$ 编号。这片海岸可以看作一条数轴，每个灯塔可以看作数轴上的一个点。第 $i$ 个灯塔在数轴上的位置为 $x_i$，每个位置上最多只能有一个灯塔。这 $n$ 个灯塔按照位置从前到后的顺序排列，即第 $x_i < x_{i+1}, 1 \le i < n$。现在，刚好有 $n$ 名游客正在海岸外排队等候进入海岸，第 $i$ 名游客进入第 $i$ 座灯塔参观。出于安全考虑，每座有游客在上面的灯塔必须被*照亮*。但由于海岸上的供能限制，最多只能*点亮* $t$ 座灯塔。每个灯塔的照明范围为 $q$。当某个灯塔上的灯打开后，海岸上和它距离不超过 $q$ 位置都会被照亮（即集合 $\{x \mid \lvert x-x_i \rvert \le q\}$ 中的所有点都会被照亮）。现在你作为海岸的旅游局的管理者，需要决定让哪些游客进入海岸玩耍。做决策不是拍脑袋想出来的，必须满足几点要求： - 保证安全第一原则，即可以找到一种照明方案使得进入海岸的每个游客所在的灯塔都被照明； - 保证先来后到原则，排在队列前面的游客优先进入海岸。如果某个游客不能进入海岸，则排在他后面的游客都不能进入海岸； - 保证追求利润原则，卖出尽可能多的门票，即尽量让数量更多的游客进入海岸。精打细算的你一敲键盘，算出最后会有多少游客进入海岸。 ## Input 第一行为三个整数 $n,t,q$，表示灯塔的数目以及最多点亮的灯塔的数目。第二行为 $n$ 个整数，第 $i$ 个数 $x_i$ 表示第 $i$ 座灯塔的坐标。 ## Output 输出一行一个整数，表示最后进入海岸的游客数目。 [samples] ## Note **【样例解释 1】** 可让前两名游客进入海岸，并点亮第一座灯塔。可以证明没有比这人数还要多的合法方案。 **【样例解释 2】** 可让前三名游客进入海岸，并点亮第二座灯塔。可以证明没有比这人数还要多的合法方案。 **【子任务】** | 子任务编号 | $n\le$ | $t \le $ | $q \le $ | 分值 | |:--:|:--:|:--:|:--:|:--:| | 1| $100$ | $100$ | $10^9$ | 20 | |2| $10^3$ | $10^3$ | $10^9$ | 20 | |3| $10^4$ | $10^4$ | $10^9$ | 20| |4| $10^5$ | $10^5$ | $10^9$ | 20 | |5| $7.5\times10^6$ | $7.5\times10^6$ | $10^9$ | 20 |

Samples

Input #1

3 1 2
1 3 6

Output #1

Input #2

3 1 3
1 3 6

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[THUSC 2019] 紧急决策",
    "description": {
      "content": "在一片海岸上，有 $n$ 个灯塔，从 $1$ 到 $n$ 编号。这片海岸可以看作一条数轴，每个灯塔可以看作数轴上的一个点。第 $i$ 个灯塔在数轴上的位置为 $x_i$，每个位置上最多只能有一个灯塔。这 $n$ 个灯塔按照位置从前到后的顺序排列，即第 $x_i < x_{i+1}, 1 \\le i < n$。现在，刚好有 $n$ 名游客正在海岸外排队等候进入海岸，第 $i$ 名游客进入第 $i$ ",
      "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": "LGP10341"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在一片海岸上，有 $n$ 个灯塔，从 $1$ 到 $n$ 编号。这片海岸可以看作一条数轴，每个灯塔可以看作数轴上的一个点。第 $i$ 个灯塔在数轴上的位置为 $x_i$，每个位置上最多只能有一个灯塔。这 $n$ 个灯塔按照位置从前到后的顺序排列，即第 $x_i < x_{i+1}, 1 \\le i < n$。现在，刚好有 $n$ 名游客正在海岸外排队等候进入海岸，第 $i$ 名游客进入第 $i$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments