第一问O(n)方法求调(不算排序) HELP!!!
查看原帖
第一问O(n)方法求调(不算排序) HELP!!!
1054952
zzCX_df楼主2024/11/26 13:01
#include <bits/stdc++.h>

using namespace std;

struct Node {
	int d, v, a;
} p[100001];
int T, n, m, L, V, ans, pos[100001], s[1000001];
bool l[1000001];

inline int speedad(int v1, int v0, int a) {
	return (v1 * v1 - v0 * v0) / (2 * a) + 1;
}

inline int speedsu(int v1, int v0, int a) {
	return (v1 * v1 - v0 * v0) / (2 * a) * (2 * a) == (v1 * v1 - v0 * v0) ? (v1 * v1 - v0 * v0) / (2 * a) - 1 : (v1 * v1 - v0 * v0) / (2 * a);
}

inline void init() {
	ans = 0;
	memset(s, 0, sizeof(s));
	memset(p, 0, sizeof(p));
	memset(pos, 0, sizeof(pos));
	memset(l, false, sizeof(l));
	scanf("%d%d%d%d", &n, &m, &L, &V);
	L++;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &p[i].d, &p[i].v, &p[i].a);
		p[i].d++;
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &pos[i]);
		pos[i]++;
	}
	sort(pos + 1, pos + m + 1);
	for (int i = 1; i <= m; i++)
		l[pos[i]] = true;
	for (int i = 1; i <= L; i++, s[i] += s[i - 1])
		if (l[i])
			s[i]++;	
}

int main() {
	scanf("%d", &T);
	for (; T--; ) {
		init();
		for (int i = 1; i <= n; i++) {
			if (p[i].a >= 0) {
				if (!p[i].a) {
					if (p[i].v > V && s[L] - s[p[i].d - 1] >= 1)
						ans++;
					continue;
				}
				int x = speedad(V, p[i].v, p[i].a);
				if (p[i].d + x <= L)
					if (s[L] - s[p[i].d + x - 1] >= 1)
						ans++;
			} else {
				int x = speedsu(V, p[i].v, p[i].a);
				if (x <= 0) {
					if (!x && s[p[i].d] - s[p[i].d - 1] >= 1) 
						ans++;
					continue;
				}
				if (p[i].d + x <= L)
					if (s[p[i].d + x] - s[p[i].d - 1] >= 1)
						ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

about the first question……

2024/11/26 13:01
加载中...