P9110

Mason123456 · 2024-01-27 19:36:39 · 题解

P9110

题面解释

有 n 辆车在 t_i 出发，对于 r_i，当 r_i 为 1 时，车从 (w_i,0) 开始往上走，当 r_i 为 2 时，车从 (0,w_i) 开始往右走。

思路

开桶。

因为出发时间不同，需要在放进桶时 w_i 需减去 t_i，再看对于不同方向的车有没有 x_i = y_i，若有，去除两个方向中车最少的（不排除 n 辆车并排走）。

CODE

注意：为防止 w_i - t_i 数组越界，统一加上 >10^6 的数，然后建议开大数组。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e7 + 10;
const int M = 1e6 + 5;
int x[N], y[N];
int main(){
    int n;
    cin>>n;
    for(int i = 1;i <= n;i++){
        int r, w, t;
        cin>>r>>w>>t;
        if(r == 1){// 向上 
            y[w - t + M] ++;
        }
        else{// 向右 
            x[w - t + M] ++;
        }
    }

    int ans = 0;
    for(int i = 0;i <= N;i++){
        if(x[i] && y[i]){
            ans += min(x[i], y[i]);
        }
    }
    cout<<ans;
}