UOJ #10 pyx的难题

pyx的难题
被这题搞得生无可恋.
容易看出

  • 题目完成时间与优先级之间的关系是单调的,故可以二分答案.
  • 用于二分的答案可以取\(O(n)\)个离散值, 这样就很方便地保证了优先级各不相同.
  • 可以用优先队列模拟, \(O(n\log(n))\)判断.
  • 总复杂度是\(O(n \log^2(n))\), 只能通过90%的数据, 对\(n \sim 3 \times 10^5\)会超时.

想了两个常数优化, 发现写起来比较麻烦, 而且貌似并不能有效降低复杂度.

上一篇:java并发编程的艺术——第四章总结


下一篇:java web 学习 --第八天(Java三级考试)