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]); //当车行驶到这里时提速到Vif (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;
}