A
每道题有做出的时长 \(t\)，价值为 \(k\)，你需要求最大的 \(c(c\in [0,1])\)：
若 \(T=\sum t\)，设一道题做出的时间为 \(x\)，那么分数为 \(f(i,x,c)=k_i(1-\dfrac{cx}{T})\)，
在分数和最大的情况下，任意一种办法，使得每道题最终得分大小关系和价值大小关系一样。
\(n\le 2e5\).
明显的二分，check 考虑贪心，邻项交换法：令 \(i\) 先选于 \(j\) 更优。
那么 \(f(i,x+t_i,c)+f(j,x+t_i+t_j,c)>f(j,x+t_j,c)+f(i,x+t_i+t_j,c)\).
计算出 \(\dfrac{k_i}{t_i}>\dfrac{k_j}{t_j}\)。那么最优策略就是按 \(\dfrac{k}{j}\) 排序。
我们按照 \(k\) 从大到小扫一遍，看是否存在不递增。
但是若 \(\dfrac{k}{t}\) 相等的，是可以任意排的，所以我们处理出 \(\dfrac{k}{t}\) 相等的，最高和最低得分即可。
B
平面直角坐标系你要从点 A 到 B，有若干矩形障碍物不能通过，但可以沿着边缘走过。
每个矩形没有重合点，询问最短路。\(n\le 2e5,x,y\le 1e8\).
发现 \(x,y\) 至少有一维是单调的。我们先考虑一直往右走的情况。
发现有用的路径只有矩形的边缘，所以向右走，遇到障碍就向上或向下。
类似扫描线，一列一列加入，用 set 维护当前有用的位置的最短路。
C
你需要求一个仙人掌邻接矩阵的行列式。 \(n\le 1e5\).
标签：LGJ,le,19,dfrac,2e5,2023.2,矩形 From： https://www.cnblogs.com/Simon-Gao/p/18022380