[CSP-S 2024] 超速检测
2024年12月25日大约 4 分钟
【20 分】
#include <bits/stdc++.h>
using namespace std;
int T;
const int MAXN = 100000; // MAXM
// 车的数量、测速仪数量、主干道长度、限速
int n, m, L, V;
// 第 i 辆车的初始位置、初始速度、加速度
int d[MAXN + 5], v[MAXN + 5], a[MAXN + 5];
// 测速点的位置
int p[MAXN + 5];
// A 性质
void subtaskA()
{
// p 保证了有序，最后一个测速点就是 p[m]
int ans1 = 0; // 超速车的数量
int ans2 = m; // 可以关闭多少台
for (int i = 1; i <= n; i++)
// 超速了且在最后测速点之前抄的
if (v[i] > V && d[i] <= p[m])
ans1++;
if (ans1 != 0)
ans2--;
cout << ans1 << " " << ans2 << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
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];
subtaskA();
}
return 0;
}【40 分】
#include <bits/stdc++.h>
using namespace std;
int T;
const int MAXN = 100000; // MAXM
// 车的数量、测速仪数量、主干道长度、限速
int n, m, L, V;
// 第 i 辆车的初始位置、初始速度、加速度
int d[MAXN + 5], v[MAXN + 5], a[MAXN + 5];
// 测速点的位置
int p[MAXN + 5];
// AB 性质
// 检查在 d 的位置开始，以 v 的初速度，a 的加速度
// 到 p 的位置的时候是否会超速
bool check(int d, int v, int a, int p)
{
if (d > p)
return false;
int s = p - d; // 位移
// sqrt(v*v + 2*a*s) > V
return v * v + 2 * a * s > V * V;
}
void subtaskAB()
{
// p 保证了有序，最后一个测速点就是 p[m]
int ans1 = 0; // 超速车的数量
int ans2 = m; // 可以关闭多少台
for (int i = 1; i <= n; i++)
// 超速了且在最后测速点之前抄的
if (check(d[i], v[i], a[i], p[m]) && d[i] <= p[m])
ans1++;
if (ans1 != 0)
ans2--;
cout << ans1 << " " << ans2 << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
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];
subtaskAB();
}
return 0;
}【100 分】算完每辆车的超速区间，然后就是一个经典贪心了
#include <bits/stdc++.h>
using namespace std;
int T;
const int MAXN = 100000; // MAXM
// 车的数量、测速仪数量、主干道长度、限速
int n, m, L, V;
// 第 i 辆车的初始位置、初始速度、加速度
int d[MAXN + 5], v[MAXN + 5], a[MAXN + 5];
// 测速点的位置
int p[MAXN + 5];
// 返回当前属性下的超速区间（位置）
vector<pair<int, int>> line; // 所有超速区间
// 超速区间按照结束位置排序
bool cmp(pair<int, int> a, pair<int, int> b)
{
return a.second < b.second;
}
void work()
{
line.clear();
// 算出所有超速区间
for (int i = 1; i <= n; i++)
{
if (a[i] == 0)
{
// 不超速
if (v[i] <= V)
continue;
// 整个路程都超速
line.push_back(make_pair(d[i], L));
}
else if (a[i] > 0)
{
// 算算啥时候开始超速
if (v[i] > V) // 一开始就超速
line.push_back(make_pair(d[i], L));
else
{
// 算算走多久之后开始超过 V 的速度
// 可以想想这里为什么可以规避浮点运算
int s = (V * V - v[i] * v[i]) / (2 * a[i]) + 1;
if (d[i] + s <= L)
line.push_back(make_pair(d[i] + s, L));
}
}
else if (a[i] < 0)
{
// 一开始就不超速，肯定不可能再超速了
if (v[i] <= V)
continue;
// 算算最后的超速位置
// 可以想想这里的细节，为什么是上取整减一
// 注意这里不能写 + (2 * a[i] - 1) 来实现，因为这边分子分母是负数
int s = (V * V - v[i] * v[i]) / (2 * a[i]);
if ((V * V - v[i] * v[i]) % (2 * a[i]) == 0)
s--;
if (s < 0)
s = 0;
line.push_back(make_pair(d[i], min(L, d[i] + s)));
}
}
// 调试
/*
for (auto x : line)
{
cout << x.first << "~" << x.second << "\n";
}
*/
sort(line.begin(), line.end(), cmp);
int pos = 1; // 下一个考虑的测速点下标
int last = -1; // 最新选上的测速点位置
int ans1 = 0; // 超速车数量
int ans2 = 0; // 需要开启的测速点数量
for (int i = 0; i < line.size(); i++)
{
// 如果当前区间已经有启用了的测速点，超速车多一台，不用新测速点
if (line[i].first <= last)
{
ans1++;
continue;
}
// 找到最后一个可行的测速点，下一个测速点没超过右端点就变为下一个
while (pos < m &&
p[pos + 1] <= line[i].second)
pos++;
// 看看这个测试点要不要启用
if (pos <= m &&
line[i].first <= p[pos] &&
p[pos] <= line[i].second)
{
last = p[pos]; // 更新最新测速点位置
pos++; // 下一个要考虑后面的测速点了
ans1++; // 这辆车会被检测超速
ans2++; // 选用了一个测速点
}
}
cout << ans1 << " " << m - ans2 << '\n';
}
int main()
{
freopen("detect.in", "r", stdin);
freopen("detect.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
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];
work();
}
return 0;
}