从暴力到优化

做题的正常路径是：先写出能保证做对的笨办法，再看数据范围决定要不要优化、优化到什么程度。一上来就憋最优解，容易想不出、或想岔了写一堆 bug 卡死。先写暴力有三重价值：一是至少拿到部分分（很多题分档给分，暴力能过小数据）；二是它天然是你的对拍标准答案（下一节），用来验证优化版对不对；三是暴力常常暴露出问题的结构和瓶颈，优化方向往往就藏在"暴力里哪一步最慢"。

判断要不要优化，看数据范围反推允许的复杂度：

// n <= 20      -> O(2^n) 暴搜 / 状压 就行
// n <= 1000    -> O(n^2) 能过
// n <= 1e6     -> 只能 O(n) 或 O(n log n)

比如暴力是 $O(n^2)$ 而 $n\le 10^6$，那就知道必须优化到 $O(n\log n)$，目标明确。坑：别在小数据的题上过度优化浪费时间；也别在大数据题上交个暴力就走——先估清楚复杂度再动手。