如果你 WA on #5,6(附带简洁写法)
查看原帖
如果你 WA on #5,6(附带简洁写法)
704668
WZWZWZWY楼主2024/11/25 07:47

如果你 WA on #5,6,看看是不是 a[i]>0a[i]>0 的情况中,没有判断位移小于 00 的情况。

另外此题有肥肠煎蛋(非常简单)的写法,但题解区似乎没有?

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;

struct node {
	int l, r;
} cs[N]; // 超速的车 

int d[N], v[N], a[N], p[N];

bool cmp(node a, node b) {
	return a.r < b.r;
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(0);
	int T; cin >> T;
	while (T--) {
		int n, m, L, V; 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];
		
		int cnt = 0;
		
		for (int i = 1; i <= n; i++) {
			if (a[i] == 0) {
				if (v[i] > V) {
					int l = lower_bound(p + 1, p + 1 + m, d[i]) - p;
					if (l <= m) cs[++cnt].l = l, cs[cnt].r = m;
				}
			} else if (a[i] > 0) {
				double x = (V * V - v[i] * v[i]) / (2.0 * a[i]); // 位移
				if (x < 0) x = -1; // 因为用的upper_bound所以设为-1 
				int l = upper_bound(p + 1, p + 1 + m, d[i] + x) - p;
				if (l <= m) cs[++cnt].l = l, cs[cnt].r = m;
			} else if (a[i] < 0) {
				if (v[i] < V) continue;
				double x = (V * V - v[i] * v[i]) / (2.0 * a[i]); // 位移
				int l = lower_bound(p + 1, p + 1 + m, d[i]) - p;
				int r = lower_bound(p + 1, p + 1 + m, d[i] + x) - p - 1;
				if (r >= l) cs[++cnt].l = l, cs[cnt].r = r;
			}
		}
		
		cout << cnt << " ";
		
		sort(cs + 1, cs + 1 + cnt, cmp);
		
		int r = 0, ans = 0;
		for (int i = 1; i <= cnt; i++) {
			if (r < cs[i].l) {
				r = cs[i].r;
				ans ++;
			}
		}
		cout << m - ans << "\n";
	}
	return 0;
}

2024/11/25 07:47
加载中...