P4443.第1题-合理安排会议

1000ms

Tried: 312

Accepted: 117

Difficulty: 6

所属公司 : 华为

算法与标签>贪心算法

题目内容

你是部门秘书，每天你需要根据会议申请表安排会议。

部门所在大楼有 $F$ 层，每层 $M$ 间会议室，每间会议室仅可安排 $1$ 场会议，每场会议耗时 $2$ 单位。

每条会议申请对应 $1$ 场会议并占用 $1$ 间会议室，申请人只会申请自己所在楼层会议室，会议可安排在申请楼层或下方楼层。安排在下方楼层由于人员赶路也会增加耗时，每移动 $1$ 层楼耗时 $1$ 单位。

请根据会议申请表，合理安排会议，让部门会议最高效，即总消耗人时最小。如果申请表无法满足，返回 $-1$ 。每场会议消耗人时 $=$ 申请人数 $×$ (会议耗时+移动楼层耗时)

输入描述

第 $1$ 行是: $F$ $M$ $N$ ，其中 $F$ 为大楼层数，范围为 $(0,1000]$ 。 $M$ 为每层会议室间数，范围为 $(0,100]$ 。 $N$ 为申请会议表长度，范围为 $(0,100000]$ 。

第 $2$ 行是: $R_1$ $P_1$ ，其中 $R_1$ 为第 $1$ 条申请的申请会议室楼层，范围为 $(0,F]$ 。 $P_1$ 为第 $1$ 条申请的会议人数，范围为 $(0,50]$ 。

第 $N+1$ 行是: $R$ $N$ $P$ ，其中 $R_N$ 为第 $N$ 条申请的申请会议室楼层， $P_N$ 为第 $N$ 条申请的会议人数。

输出描述

总消耗人时

样例1

输入

1 1 2
1 10
1 20

输出

-1

说明

部门有 $1$ 层楼，每层 $1$ 间会议室，会议申请表有 $2$ 条申请会议窒数量无法满足申请表，返回 $-1$

样例2

输入

输出

说明

部门有 $4$ 层楼，每层 $1$ 间会议室，会议申请表有 $3$ 条申请。

第 $1$ 条会议申请希望在 $3$ 楼开会， $10$ 人参与。

第 $2$ 条会议申请希望在 $1$ 楼开会， $10$ 人参与。

第 $3$ 条会议申请希望在 $3$ 楼开会， $20$ 人参与。

由于有 $2$ 场会议申请在 $3$ 楼，会议室不够分配。

如果将第 $1$ 条会议申请的会议室向下安排到 $2$ 楼，其他会议安排楼层与申请楼层保持不变。

总消耗人时为

10 \times (2+1) + 10 \times 2 + 20 \times 2 = 90

如果将第 $3$ 条会议申请的会议室向下安排到 $2$ 楼，其他会议室安排楼层与申请楼层保持不变。

总消耗人时为

10 \times 2 + 10 \times 2 + 20 \times (2+1) = 100

故选择将第 $1$ 条会议申请的会议室向下分配到 $2$ 楼更合理。

样例3

输入

输出

说明

部门有 $3$ 层楼，每局 $3$ 间会议室，会议申请表有 $4$ 条申请

第 $1$ 条会议申请希望在 $2$ 楼开会， $20$ 人参与

第 $2$ 条会议申请希望在 $1$ 楼开会， $10$ 人参与

第 $3$ 条会议申请希望在 $2$ 楼开会， $10$ 人参与

第 $4$ 条会议申请希望在 $2$ 楼开会， $10$ 人参与

总消耗人时为 $20×2+10×2+10×2+10×2$

输入

预期输出（选填）

解题思路

P4443.第1题-合理安排会议

题目内容

输入描述

输出描述

样例1

样例2

样例3

Status

Development

Support

About