大家一起吃饭的时候,总是小红先付钱,然后大家再把钱转给小红。 现在小红有 n 张账单,每张账单记录了有 k 个人一起吃饭,以及吃饭的消费 c ,现在小红需要计算每个人需要转给小红多少钱。 由于大家都比较喜欢整数,所以大家每张账单会转给小红 ⌈ (c/k) ⌉ , ⌈ x ⌉ 表示对 x 进行上取整。
第一行输入两个整数 n,m(1 ≤ n,m ≤ 10^5) 表示账单数和除小红外的总人数(分别用 1 到 m 表示)。 接下来 2× n 行,每 2 行表示一张账单。对于每张账单: 第一行输入两个整数 k (2 ≤ k ≤ m+1),c(1 ≤ c ≤ 10^9) 表示一起吃饭的人数,花费。 第二行输入 k-1 个整数,表示除小红外有哪些人一起吃饭。 数据保证, k 的总和不超过 2× 10^5 。
输出 m 个整数,表示每个人要给小红转账的总金额。
2 3 3 10 1 2 4 8 1 2 3
6 6 2
考点:模拟
数据规模 n ≤ 1e5 | 限制 1 秒 / 256MB | 标准输入输出
推荐方向:模拟
本题切入点
每张账单里其他人各分摊 ⌈c/k⌉,用数组累加每个人应付金额即可。
不涉及复杂算法,把题目描述的流程原样翻译成代码逐步执行即可。
思路框架(模拟 通法 · 非本题专属)
实现要点:结构上通常是一个外层循环包住若干 if/else 分支;只要状态定义清楚,正确率很高。
复杂度:时间 O(操作次数) | 空间 O(状态数)
该范式的通法易错点
对照本题
样例 1:输入 2 3 / 3 10 / 1 2 / 4 8 / 1 2 3 → 输出 6 6 2
第一张账单:第1、2个人都会给小红转4元
第二张账单:第1、2、3个人都会给小红转2元
因此答案为4+2=6,4+2=6,2
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2023年美团秋招编程岗第三批笔试。