题外话
5赞了,我来了,但是我不光讲性质,把错解也讲一下吧。
11月4号一个激动人心的日子。
5:30,初评成绩发布我考了502分。
5:40,终于查到分了J260,估分没错。S220,我感到意外洛谷测的是50呀。
11月6好我找到了代码。
一交果然AC,一看官方数据,我连忙将50分代码提交,AC!!!
CCF数据越来越水了。
正文
上题
先讲AB性质
首先将 p 排序。
因为不会减速所以肯定保留最后一个测速仪。
然后根据公式看看那是有没有超速,还要注意出发位置必须在前一个测速仪前。
然后关掉数量就是 m-1 ,特殊的如果一个没超速就是 m 。
还有公式的话有可能有精度问题,我们可以让两边同时乘上 2\times a 。
核心代码
int u=V*V-v[i]*v[i];
if(d[i]<=p[m]&&p[m]*(2*a[i])>d[i]*(2*a[i])+u) s++;
下面就是正解(错解)了。
核心思想是二分+贪心。
首先将 p 排序。
下面的 c 数组是超速区间。
我们可以分类讨论如果 a_i≥0 。
首先确保它超速,然后超速区间的右端点是 m ,左端点可以二分得到。
if(a[i]>=0)
{
int u=/*公式上面AB性质里有些*/;
if(/*公式*/)
{
s++;
int l=1,r=m;
while(l<r)
{
int mid=(l+r)/2;
if(/*公式和上面类似自己写*/) r=mid;
else l=mid+1;
}
c[s].l=r;
c[s].r=m;
}
}
对于 a_i<0 的情况。
我们先特判 v_i<V 那肯定不可能超速。
然后我们找到满足 p_j≥d_i 的最小的 j ,然后看看超不超速,然后再二分满足超速的右端点。
然后将 c 数组按右端点排序(贪心都学过吧,这是经典题)。
然后准备一个 q 表示上一个选的测速仪,然后就是如果左端点 <q 直接跳过,要不然就找到满足 < 右端的,然后就是贪心的选最靠右的测速仪。
q=-10000000;
top=1;
p[m]=10000000;
for(int i=1;i<=s;++i)
if(c[i].l<=q) continue;
else
{
ans++;
while(top+1<=c[i].r) top++;
q=top;
}