← 返回题目列表

AtCoder · awc0035_d

D. 兼职工作轮班分配

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥担任学园祭的执行委员会主席,并聘请了 N 兼职工作人员。每位工作人员 i (1 \leq i \leq N) 有工作效率 V_i,代表他们每小时可以完成的工作量。

学园祭当天, M 工作岗位已经出现。每份工作 j (1 \leq j \leq M) 有所需的工作量 D_j 和时间限制 T_j 完成时间。

高桥决定是否为每项工作分配一名工作人员。有些工作人员不分配任何工作是可以接受的,有些工作不分配人员而残缺不全也是可以接受的。但是,同一名工作人员不能被分配到多个工作岗位。也就是说,每个工作人员最多可以处理 1 工作。

当工作人员 i 已分配给作业 j,作业所需的时间为 D_j / V_i 小时。只有在要求的时间不超过时限的情况下,即只有当 D_j / V_i \leq T_j (相当于, V_i \times T_j \geq D_j)满意。不满足此条件的工作人员不能被分配到该工作。

确定高桥优化分配人员时可以完成的最大工作数量。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
  • 所有输入均为整数

输入

N M
V_1 V_2 \ldots V_N
D_1 T_1
D_2 T_2
\vdots
D_M T_M
  • 第一行包含 N,工作人员人数,以及 M,作业数,以空格分隔。
  • 第二行包含工作效率 每个工作人员的 V_1, V_2, \ldots, V_N ,以空格分隔。
  • 以下 M 行提供有关每个作业的信息。
  • 的 (2 + j)- 第行包含所需的工作负载 D_j 和时间限制 T_j 的 j第一个作业,以空格分隔。

输出

在一行中输出可以完成的最大作业数。


示例输入 1

3 3
5 3 7
10 2
15 3
6 1

示例输出 1

2

示例输入 2

4 5
2 4 6 8
12 2
20 5
8 1
24 4
30 3

示例输出 2

3

示例输入 3

6 7
10 20 15 5 25 30
100 5
50 2
200 10
75 3
150 6
300 15
80 4

示例输出 3

3