求调,30'(错在后面的集合覆盖贪心),目标上60
查看原帖
求调,30'(错在后面的集合覆盖贪心),目标上60
1410648
huqy444666楼主2024/11/10 08:41

我是把答案全集合到最后输出的,ANS是答案数组,主要错在后面的集合覆盖贪心,目标上60

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 6;
int T, n, m, L, V, ANS[N][2];
bool f[N];
struct car
{
	int d, v, a;
	void input() {cin >> d >> v >> a;}
}
c[N];
struct velo
{
	vector <int> t;
}
vl[N];
double speed(int v, int a, int s) 
{
	if (v * v + a * s * 2 <= 0) return -1; 
	return sqrt(v * v + 2 * a * s);
}
void fmain(int tim)
{
	memset(vl, 0, sizeof vl);
	memset(c, 0, sizeof c);
	memset(f, 0, sizeof f);
	cin >> n >> m >> L >> V;
	for (int i = 1; i <= n; i++) c[i].input();
	for (int i = 1, p; i <= m; i++)
	{
		cin >> p;
		for (int j = 1; j <= n; j++)
		{
			int d = c[j].d, v = c[j].v, a = c[j].a;
			int s = p - d;
			if (s < 0) continue;
			double sp = speed(v, a, s);
			if (sp == -1 || sp <= V) continue;
			f[j] = 1;
			vl[i].t.push_back(j);
		}
	}
	ANS[tim][0] = accumulate(f + 1, f + n + 1, 0);
	int ans = m;
	while (accumulate(f + 1, f + n + 1, 0))
	{
		for (int i = 1; i <= m; i++)
			for (int j = 0; j < vl[i].t.size(); j++)
				if (!f[vl[i].t[j]]) 
				{
					vl[i].t.erase(vl[i].t.begin() + j);
					j--;
				}
		int maxi, maxsize = -1;
		for (int i = 1; i <= m; i++)
			if (int(vl[i].t.size()) > maxsize)
			{
				maxi = i;
				maxsize = vl[i].t.size();
			}
		for (int i = 0; i < maxsize; i++) 
			f[vl[maxi].t[i]] = 0;
		ans--;
	}
	ANS[tim][1] = ans;
	return;
}
int main()
{
	cin >> T;
	for (int i = 1; i <= T; i++) fmain(i);
	for (int i = 1; i <= T; i++)
		cout << ANS[i][0] << " " << ANS[i][1] << endl;
	return 0;
 } 
2024/11/10 08:41
加载中...