当前位置：首页 > news >正文

（思维题、贪心）洛谷 P11232 CSPS2024 超速检测题解

news 来源：原创 2025/7/25 21:42:13

这一题在 2024 将我击败，~~但我怎么现在才补题解~~ ……

题意

原题

思路

对于每一辆车，我们可以算出，其在距离左端点哪段位置会超速 $[l, r]$ ，那么这辆车会被 $l$ 右侧最近的测速仪到 $r$ 左侧最近的测速仪检测到。

我们维护 $L_i,R_i$ 为距离 $i$ 最近的左右测速仪距离左端点的距离，那么检测区间（距离左端点，下同）就是 $R_l,L_r]$ ，我们发现 $L_i$ 和 $R_i$ 很好维护：

for(int i=1;i<=m;i++)
{ll p;scanf("%lld",&p);L[p]=R[p]=p;
}
for(int i=1;i<=Len;i++)
if(!L[i])L[i]=L[i-1]; 
for(int i=Len-1;i>=0;i--)
if(!R[i])R[i]=R[i+1];

而对于原始的 $[l, r]$ 就需要分类讨论了。钦定 $L e n$ 表示右端点：

$a_i=0$

这是最简单的情况。如果 $v_i\le V$ ，或者 $R_{d_i}=0$ ，即车 $i$ 要走的地方没有测速仪，那么忽略；否则从 $d_i$ 开始到 $L e n$ 是超速的，会被 $R_{d_i},L_{Len}]$ 的测速仪记录。

注：之后我们将一段测速仪区间记录，可以记录仅当 $R_l\le L_r$ 。

$a_i<0$

如果 $R_{d_i}=0$ ，或者初速度 $v_i\le V$ ，那么车 $i$ 永远不会被记录，忽略。

否则，就根据题目给的公式，我们计算出车 $i$ 走多少距离速度变成 $V$ ： $cswy=\left \lfloor \dfrac{V^2-{v_i}^2}{2a_i} \right \rfloor$

这里向下取整的原因，是因为测速仪不会记录速度刚好是 $V$ 的车，而此时是减速的情况，再往前一个单位长度才算开始超速。那么如果 $V^2-{v_i}^2$ 恰能整除 $2a_i$ ，记得 cswy--。

我们计算结束超速位置 $cswz=\min(cswy+d_i,Len)$ ，测速仪区间就是 $R_{d_i},L_{cswz}]$ 。

$a_i>0$

如果 $R_{d_i}=0$ ，忽略。

若 $v_i>V$ ，因为它一直超速，所以会被 $R_{d_i},L_{Len}]$ 的测速仪记录。

否则我们计算开始超速时，位移了多少，依然是 $cswy=\left \lfloor \dfrac{V^2-{v_i}^2}{2a_i} \right \rfloor$ ，这里因为速度刚好为 $V$ 的时候不会被检测，所以 cswy++。

依然计算 $cswz=cswy+d_i$ 。如果右边没有或者 $cs w z > L e n$ ，那么永远不会记录；否则检测区间是 $R_{cswz},L_{Len}$ 。

至此可以解决第一问，答案就是可以被合法记录的检测区间的数量 $t o t$ 。

对于第二问，我们对右端点排序，贪心地计算最少要保留多少测速仪 $k e p$ ，答案就是 $m - k e p$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+9;
ll n,m,Q,tot;
string book[N];
ll rt,cnt;
struct Node
{ll ls,rs;ll val,pri;//键值 随机优先级 ll siz;//子树大小 
}T[N];
void newNode(ll x)
{cnt++;T[cnt].siz=1;T[cnt].ls=T[cnt].rs=0;T[cnt].val=x;T[cnt].pri=rand();
}
void pushup(ll u)
{T[u].siz=T[T[u].ls].siz+T[T[u].rs].siz+1;
}
void split(ll u,ll k,ll &L,ll &R)//分裂操作 
{if(u==0){L=R=0;return;}if(T[T[u].ls].siz<k){L=u;split(T[u].rs,k-T[T[u].ls].siz-1,T[u].rs,R);}else {R=u;split(T[u].ls,k,L,T[u].ls);//关键字不同了，是数量 }pushup(u);
}
ll merge(ll L,ll R)//合并两棵根为L和R的树，返回树根 
{if(!L||!R)return L|R;if(T[L].pri>T[R].pri){T[L].rs=merge(T[L].rs,R);pushup(L);return L;}else {T[R].ls=merge(L,T[R].ls);pushup(R);return R;}
}
void insert(ll x,ll val)//排序名次为x处插入val 
{ll L,R;split(rt,x,L,R);newNode(val);rt=merge(merge(L,cnt),R);
}
ll query(ll x)
{ll L,R,L2,R2,ret;split(rt,x,L,R);split(R,1,L2,R2);
//	cout<<L<<" "<<R<<" "<<L2<<" "<<R2<<endl;ret=L2;rt=merge(L,merge(L2,R2));return ret;
}
int main()
{srand(time(0));scanf("%lld",&n);for(int i=1;i<=n;i++){cin>>book[++tot];insert(i-1,tot);}scanf("%lld",&m);for(int i=1;i<=m;i++){ll pos;cin>>book[++tot];scanf("%lld",&pos);insert(pos,tot);}scanf("%lld",&Q);while(Q--){ll x;scanf("%lld",&x);cout<<book[T[query(x)].val]<<endl;}return 0;
}

题意

思路

a i = 0 a_i=0 ai​=0

a i < 0 a_i<0 ai​<0

a i > 0 a_i>0 ai​>0

代码

相关文章：

$a_i=0$

$a_i<0$

$a_i>0$