题目名称 | 3795. [USACO Open22 Gold]Apple Catching |
---|---|
输入输出 | catchapple.in/out |
难度等级 | ★★★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 22 |
题目来源 | Benjamin 于2022-11-20加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:0, 提交:0, 通过率:0% | |||
本题关联比赛 | |||
4043级NOIP2022欢乐赛9th |
关于 Apple Catching 的近10条评论(全部评论) |
---|
catchapple.in
输出文件:catchapple.out
简单对比天上下苹果了!在某些时刻,一定数量的苹果会落到数轴上。在某些时刻,$Farmer$ $John$ 的一些奶牛将到达数轴并开始接苹果。
如果一个苹果在没有奶牛接住的情况下落到数轴上,它就会永远消失。如果一头奶牛和一个苹果同时到达,奶牛就会接住苹果。每头奶牛每秒可以移动一单位距离。一旦一头奶牛接住了一个苹果,她就会离开数轴。
如果 $FJ$ 的奶牛以最优方式合作,她们总共能接住多少个苹果?
输入的第一行包含 $N$,为苹果落到数轴上的次数或 $FJ$ 的奶牛出现的次数。
以下 $N$ 行每行包含四个整数 $q_i,t_i,x_i$ 和 $n_i$。
输入保证所有有序对 $(t_i,x_i)$ 各不相同。
输出 $FJ$ 的奶牛总计能接住的苹果的最大数量。
5 2 5 10 100 2 6 0 3 2 8 10 7 1 2 4 5 1 4 7 6
10
在这个例子中,在 $t=5$ 时刻落地的 $100$ 个苹果均不能被接住。以下是一种接住 $10$ 个苹果的方式:
$FJ$ 的所有六头 $t=4$ 时刻到达的奶牛各接一个 $t=8$ 时刻落地的苹果。
$FJ$ 的一头 $t=2$ 时刻到达的奶牛接一个 $t=8$ 时刻落地的苹果。
余下三头 $t=2$ 时刻到达的奶牛各接一个 $t=6$ 时刻落地的苹果。
点击下载大样例2/3
对于 $1\sim7$ 组数据,$1\ \leq\ N\ \leq\ 20$;
对于 $8\sim12$ 组数据,$1\ \leq\ N\ \leq\ 2⋅10^5 ,0\ \leq\ t_i,x_i\ \leq\ 2000$;
对于 $100\%$ 的数据:
$1\ \leq\ N\ \leq\ 2⋅10^5 ,q_i∈\{1,2\},0\ \leq\ t_i\ \leq\ 10^9,0\ \leq\ x_i\ \leq\ 10^9,1\ \leq\ n_i\ \leq\ 10^3$;