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;
}