CF1650F Vitaly and Advanced Useless Algorithms

Vitaly 报名参加了“高级无用算法”课程。该课程共有 $n$ 个任务。Vitaly 计算出，从他报名那天起，他有 $a_i$ 小时来完成第 $i$ 个任务。也就是说，第 $i$ 个任务的截止时间是 $a_i$ 小时。数组 $a$ 已按升序排列，也就是说，任务编号与作业提交的顺序一致。 Vitaly 做事一丝不苟，他希望每个任务都能完成 $100\%$ 或更多。最初，他每个任务的完成度都是 $0\%$。 Vitaly 有 $m$ 个训练选项，每个选项最多只能使用一次。第 $i$ 个选项由三个整数 $e_i, t_i, p_i$ 描述。如果 Vitaly 选择第 $i$ 个选项，则在当前时刻后的 $t_i$ 小时后，他将把第 $e_i$ 个任务的进度提升 $p_i\%$。 例如，假设 Vitaly 有 $3$ 个任务需要完成，数组 $a = [5, 7, 8]$。假设 Vitaly 有 $5$ 个选项：$[e_1=1, t_1=1, p_1=30]$，$[e_2=2, t_2=3, p_2=50]$，$[e_3=2, t_3=3, p_3=100]$，$[e_4=1, t_4=1, p_4=80]$，$[e_5=3, t_5=3, p_5=100]$。 那么，如果 Vitaly 按如下方式准备，他就能及时完成所有任务： - Vitaly 选择第 $4$ 个选项。则在 $1$ 小时后，他将完成第 $1$ 个任务的 $80\%$。他距离第 $1$ 个任务的截止时间还有 $4$ 小时。 - Vitaly 选择第 $3$ 个选项。则在 $3$ 小时后，他将完全完成第 $2$ 个任务。此时距离第 $1$ 个任务截止还有 $1$ 小时，距离第 $3$ 个任务截止还有 $4$ 小时。 - Vitaly 选择第 $1$ 个选项。则在 $1$ 小时后，他将完成第 $1$ 个任务的 $110\%$，也就是正好在截止时间前完成第 $1$ 个任务。 - Vitaly 选择第 $5$ 个选项。他将在 $2$ 小时后完成第 $3$ 个任务，之后再过 $1$ 小时，Vitaly 将完全完成第 $3$ 个任务。 因此，Vitaly 成功地在规定时间内完成了全部课程任务，使用了 $4$ 个选项。 请帮助 Vitaly——输出 Vitaly 按正确顺序完成任务所需的选项编号。请注意：每个选项最多只能使用一次。如果有多种可行方案，可以输出任意一种。

输入的第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 10^5$），分别表示任务数量和训练选项数量。 下一行包含 $n$ 个数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每个任务的截止时间。数组 $a$ 非递减，即 $a_1 \le a_2 \le \dots \le a_n$。 接下来的 $m$ 行，每行包含三个整数 $e_i, t_i, p_i$（$1 \le e_i \le n$，$1 \le t_i \le 10^9$，$1 \le p_i \le 100$），表示如果 Vitaly 选择该选项，则在 $t_i$ 小时后，他将把第 $e_i$ 个任务的进度提升 $p_i\%$。选项按输入顺序编号，从 $1$ 到 $m$。 保证所有测试用例中 $n+m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，第一行输出一个整数 $k$，表示 Vitaly 能够按时完成每个任务所需的选项数量。如果无法按时完成所有任务，输出 $-1$。 如果存在可行方案，下一行输出 $k$ 个不同的整数，表示所选选项的编号，顺序为使用顺序。如果有多种可行方案，可以输出任意一种。

由 ChatGPT 4.1 翻译