P11232 - 洛谷保存站

# 思路

首先，对于增速的 $a_i \ge 0$ 先扔在一边。对于 $a_i < 0$ 先求出他最后是在哪一个检测器被检测为超速的，检测器的位置记为 $p_i$。 对于一队二元组 $i,j$，如果 $p_i < p_j$，只要车 $j$ 的起始位置 $d_j \le p_i$，就也会被检测。贪心一下，对于 $p$ 按从小到大的顺序排一个序，考虑完在排序下的 $p_1$ 到 $p_{i -1}$ 的选择留下方案后，若此时车 $i$ 还不能被检测，选择 $p_i$ 留下，检测车 $i$。贪心之所以成立是因为只要在 $p_i$ 最大化的情况下能对于起点位置能够使更多的 $d_j \le p_i(i < j)$。但 $a_i \ge 0$ 的情况呀是要管的，对于最右边的能被检测到的 $a_i \ge 0$ 最靠右的起始位置，若当前 $p$ 的选择留下集合的最大值 **小于** 最靠右的起始位置，还要留一个检测器检测，加入检测器留下集合。

第二问就是集合大小。

# code

```cpp
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 5;

int t, n, m, l, v, ans, len, ld, sum;
double p[N];

struct node{
    int d, v, a;
}d[N];

struct nodes{
    int r, d;
}f[N];

bool cmp(const nodes &ad, const nodes &bd){
    return ad.r < bd.r;
}

void solve(){
    cin >> n >> m >> l >> v;
    len = 0, ans = 0, sum = 0, ld = 0;
    for(int i = 1; i <= n; i++){
        cin >> d[i].d >> d[i].v >> d[i].a;
    }
    for(int i = 1; i <= m; i++){
        cin >> p[i];
    }
    for(int i = 1; i <= n; i++){
        if(d[i].a == 0){
            if(d[i].v > v){
                int u = lower_bound(p + 1, p + m + 1, d[i].d) - p;
                if(u <= m) ld = max(ld, u), ans++;
            }
        }
        if(d[i].a < 0){
            if(d[i].v > v){
                double s = 1.0 * (1ll * v * v - 1ll * d[i].v * d[i].v) / (2ll * d[i].a);
                int u = lower_bound(p + 1, p + m + 1, d[i].d + s) - p - 1;
                if(u > 0 && p[u] >= d[i].d){
                    ans++;
                    f[++len] = {u, d[i].d};
                }
            }
        }
        if(d[i].a > 0){
            if(d[i].v > v){
                int u = lower_bound(p + 1, p + m + 1, d[i].d) - p;
                if(u <= m) ld = max(ld, u), ans++;
            }else{
                double s = 1.0 * (1ll * v * v - 1ll * d[i].v * d[i].v) / (2ll * d[i].a);
                int u = upper_bound(p + 1, p + m + 1, d[i].d + s) - p;
                if(u <= m) ld = max(ld, u), ans++;
            }
        }
    }
    cout << ans << ' ';
    sort(f + 1, f + len + 1, cmp);
    int rd = 0;
    for(int i = 1; i <= len; i++){
        if(!(rd != 0 && f[i].d <= p[rd])){
            rd = f[i].r, sum++;
        }
    }
    cout << m - (sum + (rd < ld)) << '\n';
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

```

正在渲染内容...