JZTXT

CF529B Group Photo 2 (online mirror version)

发布时间 2023-10-17 19:35:37作者: 御坂夏铃

看值域这么小，考虑枚举最大高度 \(maxh\)：

  • \(h_i>maxh\) 且 \(w_i>maxh\)，不合法。
  • \(h_i>maxh\) 且 \(w_i\leq maxh\)，必须换。
  • \(h_i\leq maxh\) 且 \(w_i>maxh\)，不能换。
  • \(h_i\leq maxh\) 且 \(w_i\leq maxh\)，可换可不换。因为最多只有一半的人能躺下，所以优先换 \(w_i-h_i\) 较大的。