P11232 [CSP-S 2024] 超速检测(民间数据)
原题链接
来分析这道题,题中所说由于是匀加速直线运动,所以超速的区间一定是连续的,而且还可以被计算出来,但是要注意区间的开闭。
我们可以把超速的区间变为测速仪的分布区间。
这道题可以通过多区间贪心来实现:一条长线段上有若干条短线段(可以重复也可以不完全覆盖长线段),请在长线段上选取尽可能少的点,使得每条短线段上(含端点)都有被选取的点。
贪心实现:按照右端点排序(从小到大),然后在尽可能少的右端点初开测速仪。
代码+注释:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2, L = 1e6 + 2;
int t, n, m, l, V, tmp, ans1, ans2;
int d[N], v[N], a[N], p[N];
int lft[L], rgt[L]; //距离最近的测速仪编号
int ld[N], rd[N]; //每辆车超速区间的左、右端点
int g[N]; //所有超速的车的编号
int id; //后面贪心用的
bool cmp(int x, int y) {
return rd[x] < rd[y];
}
void solve() {
//1.常规读入+初始化
ans1 = ans2 = 0, id = -1;
cin >> n >> m >> l >> V;
for (int i = 1; i <= n; ++i)
cin >> d[i] >> v[i] >> a[i];
for (int i = 1; i <= m; ++i) {
cin >> p[i];
lft[p[i]] = rgt[p[i]] = i; //这一行是2.的步骤,提前到这
}
//2.预处理距离最近的测速仪编号
p[0] = 0, p[m + 1] = l + 1;
for (int i = 0; i <= m; ++i)
for (int j = p[i] + 1; j < p[i + 1]; ++j)
lft[j] = i, rgt[j] = i + 1;
//3.计算每辆车的超速区间(本题核心)
for (int i = 1; i <= n; ++i) {
if (d[i] > p[m]) continue; //如果驶入的位置之后没有测速仪就不理它了
if (a[i] == 0) {
if (v[i] > V) {
g[++ans1] = i;
ld[i] = rgt[d[i]];
rd[i] = m;
} //一开始就超速
} else if (a[i] > 0) {
if (v[i] > V) {
g[++ans1] = i;
ld[i] = rgt[d[i]];
rd[i] = m;
} //一开始就超速
else {
tmp = V * V - v[i] * v[i];
if (tmp % (2 * a[i]) == 0) {
tmp = d[i] + tmp / (2 * a[i]); //当车行驶到这里时提速到V
if (tmp < p[m]) {
g[++ans1] = i;
ld[i] = rgt[tmp + 1];
rd[i] = m;
} //在p[m]处恰好提速到V是不算的
} else {
tmp = d[i] + tmp / (2 * a[i]) + 1;
if (tmp <= p[m]) {
g[++ans1] = i;
ld[i] = rgt[tmp];
rd[i] = m;
}
}
} //加速了一会儿才超速
} else {
if (v[i] > V) {
tmp = v[i] * v[i] - V * V;
if (tmp % (-2 * a[i]) == 0) {
tmp = d[i] + tmp / (-2 * a[i]);
if (tmp > p[m]) {
g[++ans1] = i;
ld[i] = rgt[d[i]];
rd[i] = m;
} else {
ld[i] = rgt[d[i]];
rd[i] = lft[tmp - 1];
if (rd[i] >= ld[i]) g[++ans1] = i;
}
} else {
tmp = d[i] + tmp / (-2 * a[i]);
if (tmp >= p[m]) {
g[++ans1] = i;
ld[i] = rgt[d[i]];
rd[i] = m;
} else {
ld[i] = rgt[d[i]];
rd[i] = lft[tmp];
if (rd[i] >= ld[i]) g[++ans1] = i;
}
}
} //一开始超速,后面减速
}
}
//4.计算最少需要开启的测速仪数量(贪心)
sort(g + 1, g + 1 + ans1, cmp);
for (int i = 1; i <= ans1; ++i)
if (ld[g[i]] > id) {
id = rd[g[i]];
++ans2;
} //如果左端点没有被覆盖到,那就在右端点覆盖
cout << ans1 << " " << m - ans2 << endl;
}
int main() {
cin >> t;
while (t--) solve();
return 0;
}