- 题解
csp-s detect
- 2024-11-13 19:47:49 @
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class car
{
public:
int d,v,a;
}p[100010];
int det[100010]; //探测器位置
vector<pair<int, int>> range; //每个车的超速区间
int main()
{
//freopen("detect5.in","r",stdin);
int T;
cin >> T;
while(T--)
{
range.clear();
bool issp = true;
int n,m,v,len;
//cin >> n >> m >> len >> v;
scanf("%d%d%d%d", &n, &m, &len, &v);
for(int i = 0; i < n; i++)
{
//cin >> p[i].d >> p[i].v >> p[i].a;
scanf("%d%d%d", &p[i].d, &p[i].v, &p[i].a);
if(p[i].a != 0) issp = false;
}
for(int i = 0; i < m; i++)
{
//cin >> det[i];
scanf("%d", &det[i]);
}
//a != 0
if(!issp)
{
int cnt = 0;
//遍历每辆车
for(int i = 0; i < n; i++)
{
if(p[i].a == 0)
{
//找第一个在车前的探测器 r
int l = -1, r = m;
while(r-l > 1)
{
int mid = l+r >> 1;
if(det[mid] < p[i].d)
{
l = mid;
}
else
{
r = mid;
}
}
//防止车从来检测不到
if(r >= m || r < 0) continue;
int vv = 2*p[i].a*(det[r]-p[i].d) + p[i].v * p[i].v;
//有一个超速以后肯定会超
if(vv > v*v)
{
range.push_back({r,m-1});
cnt++;
//cout << i << endl;
}
}
else if(p[i].a > 0)
{
//找第一个在车前的探测器 r
int l = -1, r = m;
while(r-l > 1)
{
int mid = l+r >> 1;
if(det[mid] < p[i].d)
{
l = mid;
}
else
{
r = mid;
}
}
//防止车从来检测不到
if(r >= m || r < 0) continue;
int st = r;
//找第一个检测到超速的探测器 r
l = st-1, r = m;
while(r-l > 1)
{
int mid = l+r >> 1;
int vv = 2*p[i].a*(det[mid]-p[i].d) + p[i].v * p[i].v;
if(vv > v*v)
{
r = mid;
}
else
{
l = mid;
}
}
//防止从来不超速
if(r != m)
{
range.push_back({r,m-1});
cnt++;
}
}
else // a < 0
{
//找第一个在车前的探测器 r
int l = -1, r = m;
while(r-l > 1)
{
int mid = l+r >> 1;
if(det[mid] < p[i].d)
{
l = mid;
}
else
{
r = mid;
}
}
//防止车从来检测不到
if(r >= m || r < 0) continue;
int st = r;
//找第一个检测到不超速的 r
l = st-1, r = m;
while(r-l > 1)
{
int mid = l+r >> 1;
int vv = 2*p[i].a*(det[mid]-p[i].d) + p[i].v * p[i].v;
if(vv > v*v)
{
l = mid;
}
else
{
r = mid;
}
}
//防止从不超速
if(l != st-1)
{
range.push_back({st,l});
cnt++;
//cout << i << endl;
}
}
}
//贪心求区间
sort(range.begin(), range.end());
int must = 0;
int last = -1;
for(auto it = range.begin(); it != range.end(); it++)
{
if(it->first > last)
{
must++;
last = it->second;
}
else
{
last = min(it->second, last);
}
}
cout << cnt << ' ' << m-must << endl;
}
//a = 0
else
{
sort(det, det+m);
int cnt = 0;
for(int i = 0; i < n; i++)
{
if(det[m-1] < p[i].d) continue;
int vv = 2*p[i].a*(det[m-1]-p[i].d) + p[i].v * p[i].v;
if(vv > v*v)
{
cnt++;
}
}
//留最后一个就够了
if(cnt != 0) cout << cnt << ' ' << m-1 << endl;
else cout << cnt << ' ' << m << endl;
}
}
return 0;
}
0 comments
No comments so far...