希望大佬能认真帮忙调一下
查看原帖
希望大佬能认真帮忙调一下
1022282
Jefferyz楼主2024/11/5 01:29
#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-5;

const int N = 1e5 + 1;

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

int n, m, L, V;

void check_near(int x) {
	int nxt = lower_bound(p + 1, p + m + 1, d[x]) - p;
	if(nxt == m + 1) {
		near[x] = m + 1;
		return;
	}
	if(a[x] >= 0) {
		int l = nxt - 1, r = m + 1;
		while(r > l + 1) {
			int mid = (l + r) >> 1;
			int dis = p[mid] - d[x];
			double vt = sqrt(v[x] * v[x] + 2 * a[x] * dis);
			if(vt - eps > V) r = mid;
			else l = mid;
		}
		near[x] = r;
	}
	else {
		int l = nxt - 1, r = m + 1;
		while(r > l + 1) {
			bool flag = true;
			int mid = (l + r) >> 1;
			int dis = p[mid] - d[x];
			double t= - 1.0 * v[x] / a[x];
			if(v[x] * t + 0.5 * a[x] * t * t < dis) flag = false;
			double vt = sqrt(v[x] * v[x] + 2 * a[x] * dis);
			if(flag && vt - eps > V) l = mid;
			else r = mid;
		}
		if(l == nxt - 1) near[x] = -1;
		else near[x] = l;
	}
}

bool check(int pos, int b, int n) {
	int now = p[pos];
	int use = 0;
	for(int i = n; i >= 1; --i) {
		if(a[i] < 0 && near[i] != -1) {
			if(now > p[near[i]]) {
				now = p[lower_bound(p + 1, p + m + 1, d[i]) - p];
				++use;
			}
		}
	}
	return use == b;
}

int main() {
	//freopen("detect.in", "r", stdin);
	//freopen("detect.out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while(T--) {
    	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 ans = 0;
    	for(int i = 1; i <= n; ++i) check_near(i);
    	for(int i = 1; i <= n; ++i) if(near[i] != m + 1 && near[i] != -1) ++ans;
    	cout << ans << " ";
    	int pos = 0 , q = 0, dis = 0, pp = 0;
    	for(int i = 1; i <= n; ++i) if(a[i] >= 0 && near[i] != m + 1) dis = max(dis, p[near[i]]); 
		for(int i = n; i >= 1; --i) {
			if(a[i] < 0 && near[i] != -1) {
				pos = p[lower_bound(p + 1, p + m + 1, d[i]) - p], q = i, pp = lower_bound(p + 1, p + m + 1, d[i]) - p;
				break;
			}
		}
		int now = pos;
		int use = 1;
		for(int i = q - 1; i >= 1; --i) {
			if(a[i] < 0 && near[i] != -1){
				if(now > p[near[i]]) {
					++use;
					now = p[lower_bound(p + 1, p + m + 1, d[i]) - p];
				}
			}
		}
		int bestans = use;
		if(q == 0) {
			cout << m - 1 << '\n';
			continue;
		}
		if(pos >= dis) {
			cout << m - use << '\n';
			continue;
		}
		
		if(dis == 0) {
			cout << m - use;
			continue;
		} 
		int l = pp, r = m + 1;
		while(r > l + 1) {
			int mid = (l + r) >> 1;
			if(check(mid, bestans, n)) l = mid;
			else r = mid;
		}
		if(l < dis) cout << m - bestans - 1;
		else cout << m - bestans;
		cout << '\n';
	}
	return 0;
}

第一问全没问题,最少测速仪,我分类讨论,先找a<0时所需要的测速仪数,思路是左端点逆序排序贪心选左端点,和大部分题解一样,但是算出来a<0所需的测速仪一直偏小。蒟蒻因为这题T3寄了。

2024/11/5 01:29
加载中...