[YDOI R1] whk

Luogu

IDLGP10184

Time1000ms

Memory500MB

DifficultyP4

数学贪心二分O2优化洛谷比赛

小 Z 一共要卷 $n$ 门科目，第 $i$ 门科目他有且只有 $a_i$ 道题。有无数天时间，每天小 Z 可以做无数道题。如果小 Z 认为一天是有趣的，仅当他在这一天**至少**做了 $t$ 门科目的题。小 Z 想知道最多有多少天是有趣的。 ## Input 第一行，$2$ 个正整数 $n,t$。接下来一行，有 $n$ 个整数，分别 $a_1,a_2,a_3,\dots,a_{n-1},a_n$。 ## Output 一个整数，输出小 Z 认为有趣的天数的最大值。 [samples] ## Background 小 Z 要卷 whk。 ## Note Subtask 0 为 hack 数据，不计分。 **本题采用捆绑测试**。 | 子任务编号 | $n\le$ | $a_i\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $1000$ | $1000$ | 无 | $20$ | | $2$ | $5\times10^5$ | $10^5$ | $t=1$ | $10$ | | $3$ | $5\times10^5$ | $1$ | 所有 $a_i$ 值都为 $1$ | $10$ | | $4$ | $5\times10^5$ | $10^6$ | 无 | $60$ | 对于所有数据，$1\le t\le n\le5\times10^5$，$1\le a_i \le 10^6$。

Samples

Input #1

5 3 
3 2 5 1 1

Output #1

Input #2

6 4 
1 1 4 5 1 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[YDOI R1] whk",
    "description": {
      "content": "小 Z 一共要卷 $n$ 门科目，第 $i$ 门科目他有且只有 $a_i$ 道题。有无数天时间，每天小 Z 可以做无数道题。 如果小 Z 认为一天是有趣的，仅当他在这一天**至少**做了 $t$ 门科目的题。 小 Z 想知道最多有多少天是有趣的。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 512000
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10184"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 Z 一共要卷 $n$ 门科目，第 $i$ 门科目他有且只有 $a_i$ 道题。有无数天时间，每天小 Z 可以做无数道题。\n\n如果小 Z 认为一天是有趣的，仅当他在这一天**至少**做了 $t$ 门科目的题。\n\n小 Z 想知道最多有多少天是有趣的。\n\n## Input\n\n第一行，$2$ 个正整数 $n,t$。\n\n接下来一行，有 $n$ 个整数，分别 $a_1,a_2,a_3,\\dots,a_{n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments