解题思路

• 将每条申请视为一场必须安排的会议：申请楼层为 R_i，参会人数为 P_i。
• 会议只能安排在 1…R_i 的某一楼层，且每层只有 M 个会议室；每个会议室只能安排 1 场会议。
• 每场会议消耗人时：P_i * (2 + (R_i - x))，其中 x 为实际安排楼层。把式子拆开： P_i*(2 + R_i) - P_i*x。 前半部分与安排无关，是常数；为了让总人时最小，只需 最大化 ∑(P_i * x)。
• 于是得到一个经典贪心： 按楼层从高到低遍历 f = F…1，维护一个「可在当前楼层或更低楼层安排」的候选集合（即所有 R_i ≥ f 的会议）。 在楼层 f 上选择 人数最大的前 M 个会议安排在该层（用大根堆/优先队列实现）。 这样能保证较大的 P_i 被放到尽量高的楼层，从而最大化 ∑(P_i * x)。
• 若 N > F * M，总会议数超过总会议室数，无法全部安排，直接输出 -1。

核心实现：

1. 预处理常数项 base = ∑ P_i * (2 + R_i)。
2. 按 R_i 将会议分桶到各楼层。
3. 自顶向下扫描楼层，向堆加入本层的会议，弹出至多 M 个最大 P，累加 gain += P * f。
4. 答案为 base - gain。

相关算法：贪心 + 优先队列（堆）。

复杂度分析

• 每个会议仅入堆、出堆各一次。
• 时间复杂度：O((N + F) log N)；空间复杂度：O(N)。
• 在给定数据范围内可轻松通过。

代码实现

Python

# -*- coding: utf-8 -*-
import sys
import heapq

# 外部函数：根据参数计算最小总人时
def min_total_time(F, M, N, meetings):
    # 如果会议总数超过总会议室数量，无法满足
    if N > F * M:
        return -1

    # 分桶：按申请楼层收集参会人数
    buckets = [[] for _ in range(F + 1)]  # 1..F 使用
    base = 0  # 常数项 ∑ P*(2+R)
    for r, p in meetings:
        base += p * (2 + r)
        buckets[r].append(p)

    # 贪心：从高到低，每层取出人数最大的 M 个会议
    heap = []  # 使用小根堆存负数，等价于大根堆
    gain = 0   # 累加 ∑(P*x)
    for f in range(F, 0, -1):
        for p in buckets[f]:
            heapq.heappush(heap, -p)  # 负号实现大根堆
        for _ in range(M):
            if not heap:
                break
            p = -heapq.heappop(heap)
            gain += p * f

    return base - gain

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    F, M, N = data[0], data[1], data[2]
    meetings = []
    idx = 3
    for _ in range(N):
        r, p = data[idx], data[idx + 1]
        meetings.append((r, p))
        idx += 2
    ans = min_total_time(F, M, N, meetings)
    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

/**
 * ACM 风格；读取输入并输出结果；求最小总人时
 */
public class Main {

    // 外部函数：计算最小总人时
    static long minTotalTime(int F, int M, int N, int[][] meetings) {
        if (N > (long)F * M) return -1L; // 无法满足

        List<Integer>[] buckets = new ArrayList[F + 1];
        for (int i = 0; i <= F; i++) buckets[i] = new ArrayList<>();

        long base = 0; // 常数项 ∑ P*(2+R)
        for (int i = 0; i < N; i++) {
            int r = meetings[i][0], p = meetings[i][1];
            base += (long)p * (2L + r);
            buckets[r].add(p);
        }

        // 大根堆，优先安排人数多的会议到高层
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        long gain = 0; // ∑(P*x)
        for (int f = F; f >= 1; f--) {
            for (int p : buckets[f]) pq.offer(p);
            for (int k = 0; k < M && !pq.isEmpty(); k++) {
                int p = pq.poll();
                gain += (long)p * f;
            }
        }
        return base - gain;
    }

    // 简单快速读入（根据数据量选择使用）
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' '); // 跳过空白
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int F = fs.nextInt(), M = fs.nextInt(), N = fs.nextInt();
        int[][] meetings = new int[N][2];
        for (int i = 0; i < N; i++) {
            meetings[i][0] = fs.nextInt(); // R_i
            meetings[i][1] = fs.nextInt(); // P_i
        }
        long ans = minTotalTime(F, M, N, meetings);
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

/*
 * 外部函数：根据输入计算最小总人时
 */
long long minTotalTime(int F, int M, int N, const vector<pair<int,int>>& meetings) {
    if ((long long)F * M < N) return -1; // 超出会议室总量

    vector<vector<int>> buckets(F + 1); // 按申请楼层分桶
    long long base = 0; // 常数项 ∑ P*(2+R)
    for (auto &it : meetings) {
        int r = it.first, p = it.second;
        base += 1LL * p * (2 + r);
        buckets[r].push_back(p);
    }

    priority_queue<int> pq; // 大根堆
    long long gain = 0;     // ∑(P*x)
    for (int f = F; f >= 1; --f) {
        for (int p : buckets[f]) pq.push(p);
        for (int k = 0; k < M && !pq.empty(); ++k) {
            int p = pq.top(); pq.pop();
            gain += 1LL * p * f;
        }
    }
    return base - gain;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int F, M, N;
    if (!(cin >> F >> M >> N)) return 0;
    vector<pair<int,int>> meetings(N);
    for (int i = 0; i < N; ++i) {
        int r, p;
        cin >> r >> p;
        meetings[i] = {r, p};
    }
    long long ans = minTotalTime(F, M, N, meetings);
    cout << ans << "\n";
    return 0;
}

题目内容

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

部门所在大楼有 $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 13
3 10
1 10
3 20

输出

90

说明

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

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

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

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

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

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

总消耗人时为 $10×2+10×2+20×(2+1)=100$

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

样例3

输入

3 3 4
2 20
1 10
2 10
2 10

输出

100

说明

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

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

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

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

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

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