P4379 [USACO18OPEN] Lemonade Line S

这是农场上一个炎热的夏日，Farmer John 要给他的 $N$ 头奶牛发柠檬汽水了！所有的 $N$ 头奶牛（编号为 $1 \dots N$）都喜欢柠檬汽水，只是有些喜欢的程度更高一些。具体来说，奶牛 $i$ 为了获得柠檬汽水，最多愿意排在 $w_i$ 头奶牛之后。现在所有的 $N$ 头奶牛都在田里，但只要 Farmer John 敲响牛铃，这些奶牛就会立刻赶到柠檬汽水站。她们会在 Farmer John 开始分发柠檬汽水之前到达，但没有两头奶牛会在同一时刻到达。此外，当奶牛 $i$ 到达时，当且仅当队伍中至多有 $w_i$ 头奶牛时，她才会加入队伍。 Farmer John 想要提前准备一定量的柠檬汽水，但他不想浪费。排队的奶牛数量可能取决于她们的到达顺序。请帮助他求出在所有可能的到达顺序下，最小的可能排队奶牛数量。

无

无

在这个情况下，可能最后仅有三头奶牛在队伍中（这也是最小可能值）。假设 $w = 7$ 和 $w = 400$ 的奶牛先到并等在队伍中。然后 $w = 1$ 的奶牛到达并且会离开，因为已经有 $2$ 头奶牛在队伍中了。接着 $w = 2$ 的两头奶牛到达，一头留下排队，另一头离开。 供题：Dhruv Rohatgi