← 返回题目列表

AtCoder · awc0035_a

A. 仓库库存管理

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

分数: 266 分

问题陈述

高桥在一家公司的物流部门工作。公司拥有 N 仓库,从仓库编号 1 到仓库 N。各仓库 i (1 \leq i \leq N) 目前存储 P_i 项目。

今天, M 已发出在仓库之间移动物品的运输指令。的 j-th (1 \leq j \leq M) 运输指令是“移动 W_j 仓库中的物品 U_j 到仓库 V_j。”在这里, U_j \neq V_j。同一对仓库之间可能存在多个发货指令。

的 M 运输说明是一次性应用的,而不是按顺序应用的。也就是说,每个仓库中的最终物品数量是通过获取初始物品数量,加上进入该仓库的物品总数,并减去该仓库出库的物品总数而获得的。

Takahashi 希望在应用所有发货指令后查找包含最多商品的仓库号。如果有多个仓库,物品最多,则找到仓库编号最小的一个。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j \leq N (1 \leq j \leq M)
  • 1 \leq V_j \leq N (1 \leq j \leq M)
  • U_j \neq V_j (1 \leq j \leq M)
  • 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
  • 所有输入值均为整数。
  • 保证在应用所有发货指令后,每个仓库中的物品数量为 0 或更多。

输入

N M
P_1 P_2 \ldots P_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 第一行包含仓库数量 N 和发货说明的数量 M,用空格分隔。
  • 第二行包含每个仓库中的初始物品数量 P_1, P_2, \ldots, P_N,用空格分隔。
  • 以下 M 行包含每个装运指令的详细信息。如果 M = 0,这部分没有给出。
  • 的 j第行 (1 \leq j \leq M) 包含来源仓库编号 U_j,目的仓库号 V_j,以及要移动的项目数 W_j 为 j第一条运输指令,以空格分隔。

输出

应用所有装运指令后,在一行上打印包含最多商品的仓库编号。如果有多个仓库,物品数量最多,则打印数量最少的仓库。


示例输入 1

3 2
10 20 30
1 2 5
3 2 10

示例输出 1

2

示例输入 2

3 2
10 20 10
2 1 5
2 3 5

示例输出 2

1

示例输入 3

6 5
100 200 150 300 250 50
4 2 50
1 3 30
5 6 100
2 1 80
3 5 40

示例输出 3

4

示例输入 4

10 8
500 300 800 200 600 100 450 350 700 250
3 1 200
5 7 150
9 2 300
4 6 100
1 10 400
8 3 50
7 9 100
6 5 50

示例输出 4

3

示例输入 5

1 0
1000000000

示例输出 5

1