不懂就问
查看原帖
不懂就问
739534
OI_StarGod楼主2024/10/28 12:54

原本代码如下:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int t;
int n, m, len, mv;
int d[N], v[N], a[N];
struct Car {
	int s, t;
} car[N];
int p[N];
bool cmp(Car a, Car b) {
	return a.t < b.t;
}
signed main() {
//	freopen("detect4.in", "r", stdin);
//	freopen("detect4.out", "w", stdout);
	scanf("%lld", &t);
	while (t--) {
		int cnt = 0;
		int ans = 0;
		scanf("%lld %lld %lld %lld", &n, &m, &len, &mv);
		for (int i = 1; i <= n; ++i) {
			scanf("%lld %lld %lld", &d[i], &v[i], &a[i]);
		}
		for (int i = 1; i <= m; ++i) {
			scanf("%lld", &p[i]);
		}
		for (int i = 1; i <= n; ++i) {
			int ll = 1, rr = m, sta = 0;
			while (ll <= rr) {
				int mid = (ll + rr) >> 1;
				if (p[mid] >= d[i]) {
					rr = mid - 1;
					sta = mid;
				} else {
					ll = mid + 1;
				}
			}
			if (sta == 0) {
				continue;
			}
			if (a[i] == 0) {
				if (v[i] > mv) {
					++ans;
					car[++cnt].s = sta;
					car[cnt].t = m;
				}
			} else if (a[i] > 0) {
				int l = sta, r = m, res = 0;
				while (l <= r) {
					int mid = (l + r) >> 1;
					int nv = v[i] * v[i] + 2 * a[i] * (p[mid] - d[i]);
					if (nv > mv * mv) {
						r = mid - 1;
						res = mid;
					} else {
						l = mid + 1;
					}
				}
				if (res != 0) {
					++ans;
					car[++cnt].s = res;
					car[cnt].t = m;
				}
			} else {
				int nv = v[i] * v[i] + 2 * a[i] * (p[sta] - d[i]);
				if (nv > mv * mv) {
					++ans;
					car[++cnt].s = sta;
					int l = sta, r = m, res = 0;
					while (l <= r) {
						int mid = (l + r) >> 1;
						int nv = v[i] * v[i] + 2 * a[i] * (p[mid] - d[i]);
						if (nv <= mv * mv) {
							r = mid - 1;
							res = mid;
						} else {
							l = mid + 1;
						}
					}
					if (res != 0) {
						car[cnt].t = res - 1;
					} else {
						car[cnt].t = m;
					}
				}
			}
		}
		printf("%lld ", ans);
		sort(car + 1, car + cnt + 1, cmp);
		ans = 1;
		int nt = car[1].t;
		for (int i = 2; i <= cnt; ++i) {
			if (nt < car[i].s) {
				++ans;
				nt = car[i].t;
			}
		}
		printf("%lld\n", m - ans);
	}
	return 0;
}

70pts

改完后是

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int t;
int n, m, len, mv;
int d[N], v[N], a[N];
struct Car {
	int s, t;
} car[N];
int p[N];
bool cmp(Car a, Car b) {
	return a.t < b.t;
}
signed main() {
//	freopen("detect4.in", "r", stdin);
//	freopen("detect4.out", "w", stdout);
	scanf("%lld", &t);
	while (t--) {
		int cnt = 0;
		int ans = 0;
		scanf("%lld %lld %lld %lld", &n, &m, &len, &mv);
		for (int i = 1; i <= n; ++i) {
			scanf("%lld %lld %lld", &d[i], &v[i], &a[i]);
		}
		for (int i = 1; i <= m; ++i) {
			scanf("%lld", &p[i]);
		}
		for (int i = 1; i <= n; ++i) {
			int ll = 1, rr = m, sta = 0;
			while (ll <= rr) {
				int mid = (ll + rr) >> 1;
				if (p[mid] >= d[i]) {
					rr = mid - 1;
					sta = mid;
				} else {
					ll = mid + 1;
				}
			}
			if (sta == 0) {
				continue;
			}
			if (a[i] == 0) {
				if (v[i] > mv) {
					++ans;
					car[++cnt].s = sta;
					car[cnt].t = m;
				}
			} else if (a[i] > 0) {
				int l = sta, r = m, res = 0;
				while (l <= r) {
					int mid = (l + r) >> 1;
					int nv = v[i] * v[i] + 2 * a[i] * (p[mid] - d[i]);
					if (nv > mv * mv) {
						r = mid - 1;
						res = mid;
					} else {
						l = mid + 1;
					}
				}
				if (res != 0) {
					++ans;
					car[++cnt].s = res;
					car[cnt].t = m;
				}
			} else {
				int nv = v[i] * v[i] + 2 * a[i] * (p[sta] - d[i]);
				if (nv > mv * mv) {
					++ans;
					car[++cnt].s = sta;
					int l = sta, r = m, res = 0;
					while (l <= r) {
						int mid = (l + r) >> 1;
						int nv = v[i] * v[i] + 2 * a[i] * (p[mid] - d[i]);
						if (nv <= mv * mv) {
							r = mid - 1;
							res = mid;
						} else {
							l = mid + 1;
						}
					}
					if (res != 0) {
						car[cnt].t = res - 1;
					} else {
						car[cnt].t = m;
					}
				}
			}
		}
		printf("%lld ", ans);
		sort(car + 1, car + cnt + 1, cmp);
		ans = 0;
		int nt = 0;
		for (int i = 1; i <= cnt; ++i) {
			if (nt < car[i].s) {
				++ans;
				nt = car[i].t;
			}
		}
		printf("%lld\n", m - ans);
	}
	return 0;
}

100pts

有无大佬说一下为什么?

2024/10/28 12:54
加载中...