认为逻辑没有问题,前两个样例都过了,提交全部WA,哪位大师帮忙检查一下
查看原帖
认为逻辑没有问题,前两个样例都过了,提交全部WA,哪位大师帮忙检查一下
891817
Haiiao楼主2024/10/31 10:37

//思路:先计算速度变为V需要的距离s[i],通过分析算出每一个超速的区间,最后根据左端点排序,计算多余的超速监测站。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int INF = 1e9;
long long t, n, m, L, V;
long long d[N], v[N], a[N], p[N];
double s[N];
long long ans1, ans2;

struct node {
	long long l;
	long long r;
} dd[N];
int cnt;

bool comp(node a, node b) {
	return a.l < b.l;
}

int check(double x) {
	if (x > p[m])
		return m + 1;
	int l = 1, r = m;
	while (l < r) {
		int mid = (l + r) / 2;
		if (p[mid] > x)
			r = mid;
		else
			l = mid + 1;
	}
	return l;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> t;
	while (t--) {
		ans1 = 0, ans2 = 0;
		cin >> n >> m >> L >> V;
		memset(s, 0, sizeof(s));
		memset(dd, 0, sizeof(dd));
		cnt = 0;
		for (int i = 1; i <= n; i++) {
			cin >> d[i] >> v[i] >> a[i];
			if (a[i] > 0) {
				if (v[i] > V)
					s[i] = 0;
				else
					s[i] = (V * V - v[i] * v[i]) / (2.0 * a[i]);
			} else if (a[i] == 0) {
				if (v[i] > V)
					s[i] = 0;
				else
					s[i] = -1;
			} else {
				if (v[i] <= V)
					s[i] = 0;
				else
					s[i] = (V * V - v[i] * v[i]) / (2.0 * a[i]);
			}
		}
		for (int i = 1; i <= m; i++)
			cin >> p[i];
		sort(p + 1, p + m + 1);
		for (int i = m; i > 0 && a[i] > L; i--)
			m--;
		for (int i = 1; i <= n; i++) {
			if (s[i] == -1)
				continue;
			else if (a[i] >= 0) {
				int l = check(d[i] + s[i]);
				if (l <= n) {
					ans1++;
					dd[++cnt] = (node) {
						l, n
					};
				}
			} else {
				if (s[i] == 0)
					continue;
				else if (d[i] + s[i] < L) {
					int l = check(d[i]);
					int r = check(d[i] + s[i]);
					if (l < r || ((d[i] + s[i]) == p[r])) {
						ans1++;
						dd[++cnt] = (node) {
							l, r - 1
						};
					}
				} else {
					int l = check(d[i]);
					if (l <= n) {
						ans1++;
						dd[++cnt] = (node) {
							l, n
						};
					}
				}
			}
		}
		sort(dd + 1, dd + cnt + 1, comp);
		long long mn = INF;
		for (int i = 1; i <= cnt; i++) {
			if (dd[i].l <= mn)
				mn = min(mn, dd[i].r);
			else
				mn = dd[i].r, ans2++;

		}

		cout << ans1 << " " << m - ans2 - 1 << endl;
	}
	return 0;
}

/*
1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
*/
2024/10/31 10:37
加载中...