第二问求调
查看原帖
第二问求调
932918
zrzforrest楼主2024/11/10 23:59
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;

int T;
const int MAXN = 1e5 + 10;
const int MAXL = 1e6 + 0.001;
int n, m, l, V;

struct Car
{
	int d, v, a, id, l = MAXN - 10, r = MAXN - 11; //l,r表示能探测到该车超速的最先/后的探测器编号
	int safe;
	bool op;
	const bool operator< (const Car &rhs)
	{
		/*
		if (l != rhs.l)
		{
			return l < rhs.l;
		}
		*/
		return r < rhs.r;
	}
} CC[MAXN];
int pos[MAXN];

int main()
{
	cin >> T;
	while (T--)
	{
		int ans1 = 0;
		cin >> n >> m >> l >> V;
		for (int i = 1; i <= n; i++)
		{
			CC[i].op = 0;
			cin >> CC[i].d >> CC[i].v >> CC[i].a;
			if (CC[i].a > 0)
			{
				if (CC[i].v > V)
				{
					CC[i].safe = l;
					CC[i].op = 1;
				}
				else
				{
					if ((V * V - CC[i].v * CC[i].v) / (2 * CC[i].a) + CC[i].d <= l)
					{
						CC[i].d = (V * V - CC[i].v * CC[i].v) / (2 * CC[i].a) + CC[i].d;
						CC[i].safe = l;
						CC[i].op = 1;
					}
				}
			}
			else
			{
				if (CC[i].v > V)
				{
					if (CC[i].a != 0)
					{
						CC[i].safe = min(l, (V * V - CC[i].v * CC[i].v) / (2 * CC[i].a) + CC[i].d);
					}
					else
					{
						CC[i].safe = l;
					}
					CC[i].op = 1;
				}
			}
		}
		/*
		for (int i = 1; i <= n; i++)
		{
			cout << CC[i].d << " " << CC[i].safe << endl;
		}
		*/
		for (int i = 1; i <= m; i++)
		{
			cin >> pos[i];
		}
		//求ans1,l,r
		for (int i = 1; i <= n; i++)
		{
			if (!CC[i].op)
			{
				continue;
			}
			int l = 1, r = m;
			while (l < r)
			{
				int mid = (l + r) / 2;
				if (pos[mid] < CC[i].d)
				{
					l = mid + 1;
				}
				else
				{
					r = mid;
				}
			}
			CC[i].l = l;
			l = 1, r = m;
			while (l < r)
			{
				int mid = (l + r) / 2;
				if (pos[mid] > CC[i].safe)
				{
					r = mid - 1;
				}
				else
				{
					l = mid + 1;
				}
			}
			CC[i].r = l;
			if (CC[i].r >= CC[i].l)
			{
				ans1++;
			}
			else
			{
				CC[i].op = 0;
			}
		}
		/*
		for (int i = 1; i <= n; i++)
		{
			cout << CC[i].l << " " << CC[i].r << endl;
		}
		*/
		cout << ans1 << " ";
		int ans2 = 0;
		sort(CC + 1, CC + n + 1);
		int now = 0;
		for (int i = 1; i <= ans1; i++)
		{
			if (!CC[i].op)
			{
				continue;
			}
			if (now < CC[i].l)
			{
				ans2++;
				now = CC[i].r;
			}
		}
		cout << m - ans2 << endl;
	}
	return 0;
}
2024/11/10 23:59
加载中...