Problem 1. Empty Stalls
扫两遍即可。
Problem 2. Line of Sight
我们发现能互相看见的一对点一定能同时看见粮仓的某一段。于是转换成有n段线段,问有多少对线段相交。可以按左端点排序,用优先队列维护右端点,弹出比左端点小的。
为了方便计算对数,我们可以先做一遍,再把每个线段都+2*pi,再计数。
Problem 3. No Change
(没有看到要买的东西必须是依次的。。)
如果要依次买的话就显然可以用dp搞。
2023-12-18 10:34:16
扫两遍即可。
我们发现能互相看见的一对点一定能同时看见粮仓的某一段。于是转换成有n段线段,问有多少对线段相交。可以按左端点排序,用优先队列维护右端点,弹出比左端点小的。
为了方便计算对数,我们可以先做一遍,再把每个线段都+2*pi,再计数。
(没有看到要买的东西必须是依次的。。)
如果要依次买的话就显然可以用dp搞。