[USACO20JAN] Race B

Luogu
IDLGP9948
Time1000ms
Memory256MB
DifficultyP3
数学贪心2020二分USACOO2优化
Bessie 正在参加一场 $K$($1\le K\le 10^9$)米的跑步比赛。她从 $0$ 米每秒的速度开始比赛。在每一秒中,她可以选择将她的速度增加 $1$ 米每秒,保持速度不变,或者将她的速度减少 $1$ 米每秒。例如,在第一秒中,她可以将她的速度增加到 $1$ 米每秒,跑 $1$ 米,或者保持她的速度 $0$ 米每秒不变,跑 $0$ 米。Bessie 的速度不会降低到小于零。 Bessie 始终朝着终点线的方向跑,她想要花费整数秒的时间完成比赛。此外,她不想在终点时跑得太快:在 Bessie 跑完 $K$ 米的时刻,她希望她的速度不超过 $X$($1\le X\le 10^5$)米每秒。Bessie 想要对于 $N$($1\le N\le 1000$)个不同的 $X$ 值知道她多快可以完成比赛。 ## Input 输入的第一行包含两个整数 $K$ 和 $N$。 以下 $N$ 行每行包含一个整数 $X$。 ## Output 输出 $N$ 行,每行包含一个整数,表示 Bessie 完成比赛时的速度小于或等于 $X$ 的情况下跑完 $K$ 米需要的最小时间。 [samples] ## Note ### 样例解释 1 当 $X=1$ 时,一种最优方案为: 1. 将速度增加到 $1$ 米/秒,跑 $1$ 米 2. 将速度增加到 $2$ 米/秒,跑 $2$ 米,总计跑 $3$ 米 3. 将速度保持在 $2$ 米/秒,总计跑 $5$ 米 4. 将速度保持在 $2$ 米/秒,总计跑 $7$ 米 5. 将速度保持在 $2$ 米/秒,总计跑 $9$ 米 6. 将速度降低到 $1$ 米/秒,总计跑 $10$ 米 当 $X=3$ 时,一种最优方案为: 1. 将速度增加到 $1$ 米/秒,跑 $1$ 米 2. 将速度增加到 $2$ 米/秒,总计跑 $3$ 米 3. 将速度增加到 $3$ 米/秒,总计跑 $6$ 米 4. 将速度保持在 $3$ 米/秒,总计跑 $9$ 米 5. 将速度保持在 $3$ 米/秒,总计跑 $12$ 米 注意当 $X=3$ 时,以下方案是不合法的: 1. 将速度增加到 $1$ 米/秒,跑 $1$ 米 2. 将速度增加到 $2$ 米/秒,总计跑 $3$ 米 3. 将速度增加到 $3$ 米/秒,总计跑 $6$ 米 4. 将速度增加到 $4$ 米/秒,总计跑 $10$ 米 这是因为在 Bessie 跑完 $10$ 米的时刻,她的速度是 $4$ 米/秒。
Samples
Input #1
10 5
1
2
3
4
5
Output #1
6
5
5
4
4
API Response (JSON)
{
  "problem": {
    "name": "[USACO20JAN] Race B",
    "description": {
      "content": "Bessie 正在参加一场 $K$($1\\le K\\le 10^9$)米的跑步比赛。她从 $0$ 米每秒的速度开始比赛。在每一秒中,她可以选择将她的速度增加 $1$ 米每秒,保持速度不变,或者将她的速度减少 $1$ 米每秒。例如,在第一秒中,她可以将她的速度增加到 $1$ 米每秒,跑 $1$ 米,或者保持她的速度 $0$ 米每秒不变,跑 $0$ 米。Bessie 的速度不会降低到小于零。 Bes",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9948"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bessie 正在参加一场 $K$($1\\le K\\le 10^9$)米的跑步比赛。她从 $0$ 米每秒的速度开始比赛。在每一秒中,她可以选择将她的速度增加 $1$ 米每秒,保持速度不变,或者将她的速度减少 $1$ 米每秒。例如,在第一秒中,她可以将她的速度增加到 $1$ 米每秒,跑 $1$ 米,或者保持她的速度 $0$ 米每秒不变,跑 $0$ 米。Bessie 的速度不会降低到小于零。\n\nBes...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments