自动搬运

查看原文

来自洛谷，原作者为

	Mason123456 Nobody even cares

搬运于2025-08-24 22:45:26，当前版本为作者最后更新于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;
}