111qqz的小窝

老年咸鱼冲锋!

codeforces 314 D One-Dimensional Battle Ships (模拟)

比赛的时候没搞出来,really sad.
其实这题很容易啊....
首先,对于lie 的判断应该基于能放的船的个数.
能放的船的个数是随着射的点数的增加而减少的.
射完每个点后更新能放的船的个数,如果这个时候已经无法放下k条船了,说明lie了.
如果所有都射完也没发生,那么就-1.

由于船与串不能相邻,除了最后一条船,每条船实际占的size 应该为a+1
那么很容易知道对于长度为l的区间,能放的船的个数为(l+1)/(a+1)
这是初始能放的船的个数,为最大值.
当射了点b之后,破坏的是b所在的一段最大的没有被射过点的区间的连续性.
做法是找到距离b点最近的左端和右端的被射过的点.
可以用set 搞,找的时候upper_bound
记得初始化的时候把 0点和 n+1 点当成射过的.

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363