[SNCPC2024] 商路

Luogu

IDLGP10695

Time1000ms

Memory256MB

DifficultyP5

2024O2优化陕西Ad-hoc省赛/邀请赛

一个圆周被 $K$ 个点等分，这些点按照顺时针编号为 $1, 2, \cdots, K$。其中点 $a_1, a_2, \cdots, a_n$ 分别建造有一座市场 $M_1, M_2, \cdots, M_n$。一条从市场 $i$ 出发，目标是市场 $j$ 的商路是有向线段 $M_i M_j$ ($i \neq j$) 且必须满足以下条件： - 市场 $j$ 必须是距离市场 $i$ 最远的市场（如果有多个距离相同的最远的市场,那么任意一个均可）。 - 商路线段 $M_i M_j$ 不能与其他商路线段在起点或者终点以外的地方相交或重合。最多可以存在多少条商路？ ## Input 第一行包含两个整数 $K, n$ ($3 \leq K \leq 10^9, 3\leq n \leq \min(K,10^5) $)，由空格隔开，表示有 $n$ 个市场分布在圆周的 $K$ 等分点上。第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1\leq a_1 < a_2 < \cdots < a_{n-1} < a_n \leq K$)，为建有市场的点的编号。 ## Output 输出一个整数表示最多可以存在的商路的数量。 [samples] ## Note 对于第一个样例，其中两种可能的答案如下图所示： ![](https://cdn.luogu.com.cn/upload/image_hosting/ql7evd73.png) ![](https://cdn.luogu.com.cn/upload/image_hosting/ya5u7z3o.png)

Samples

Input #1

10 5
1 2 5 6 8

Output #1

Input #2

3 3
1 2 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[SNCPC2024] 商路",
    "description": {
      "content": "一个圆周被 $K$ 个点等分，这些点按照顺时针编号为 $1, 2, \\cdots, K$。其中点 $a_1, a_2, \\cdots, a_n$ 分别建造有一座市场 $M_1, M_2, \\cdots, M_n$。 一条从市场 $i$ 出发，目标是市场 $j$ 的商路是有向线段 $M_i M_j$ ($i \\neq j$) 且必须满足以下条件： - 市场 $j$ 必须是距离市场 $i$ 最远的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10695"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个圆周被 $K$ 个点等分，这些点按照顺时针编号为 $1, 2, \\cdots, K$。其中点 $a_1, a_2, \\cdots, a_n$ 分别建造有一座市场 $M_1, M_2, \\cdots, M_n$。\n\n一条从市场 $i$ 出发，目标是市场 $j$ 的商路是有向线段 $M_i M_j$ ($i \\neq j$) 且必须满足以下条件：\n\n- 市场 $j$ 必须是距离市场 $i$ 最远的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments