题面描述:

在一列具有$m$个座位的火车上，停靠$n$个站点，发车前有 ( x ) 名乘客预定了座位。为了确保座位的最大利用率，需要计算如何合理分配座位，并输出最大座位利用数。座位利用数是指每个座位被使用的站数，例如某座位从第 0 站到第 10 站被使用，则其利用数为 10。如果在任意时刻乘客数量超过座位数 ( m )，则分配不合适。输入包括座位数、站点数和乘客数，以及每位乘客的上车和下车站点。输出一个整数，表示最大的座位利用数。

思路

可以暴力模拟所有情况，使用二进制枚举的方法。

用0和1代表乘客不乘坐和乘坐两种情况，用一个数字可以代表所有乘客是否乘坐，枚举这个数的二进制位即可。

对于每一种情况，模拟当前是否有人乘坐对应站的对应座位，当某一站的乘客数量超过m时，就说明该情况人数太多，说明不符合条件。

直接求所有符合条件的情况的最大利用数即可。时间复杂度$O(n * x * 2^x$)$

题解

我们需要解决的问题是如何合理安排乘客的座位，使得座位利用率达到最大。给定一列火车有 ( m ) 个座位，停靠 ( n ) 个站点，且有 ( x ) 名乘客预定了座位。每名乘客有自己的上车和下车站点。我们可以使用二进制枚举的方法，尝试每一种可能的乘客组合来计算最大座位利用数。

方法

1. 二进制枚举：

   • 使用一个整数 ( i ) 从 0 到 ( 2^x - 1 ) 进行遍历，( i ) 的每一位代表一名乘客是否选择乘坐（1 表示乘坐，0 表示不乘坐）。
   • 例如，对于 ( x = 3 ) 的情况，数字 5（即二进制的 101）表示第一和第三位乘客选择乘坐，而第二位乘客不乘坐。

2. 座位利用模拟：

   • 对于每一个乘客组合，我们需要记录每个站点上有多少乘客上车。
   • 当某一站的乘客数量超过 ( m ) 时，该组合不符合条件，直接跳过。
   • 否则，计算该组合的座位利用数，即所有被选择乘客的下车站点减去上车站点的总和。

3. 更新最大利用数：

   • 对每一种符合条件的组合，更新最大座位利用数。

代码

Java

import java.util.*;

public class Main {

    // 定义一个 Pair 类，用于存储乘客的上下车站点
    static class Pair {
        int x, y; // x 为上车站点，y 为下车站点

        // Pair 类的构造函数
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void solve() {
        Scanner scanner = new Scanner(System.in); // 创建扫描器对象，用于输入
        int m = scanner.nextInt(); // 读取座位数
        int n = scanner.nextInt(); // 读取站点数
        int x = scanner.nextInt(); // 读取乘客数
        
        List<Pair> a = new ArrayList<>(); // 存储乘客的上下车站点
        for (int i = 0; i < x; ++i) {
            int first = scanner.nextInt(); // 读取上车站点
            int second = scanner.nextInt(); // 读取下车站点
            a.add(new Pair(first, second)); // 将上下车信息存入列表
        }
        
        int ans = 0; // 用于记录最大座位利用数
        
        // 枚举所有可能的乘客组合
        for (int i = 0; i < (1 << x); ++i) {
            int[] cnt = new int[n]; // 记录每个站点的乘客数量
            boolean ok = true; // 用于标记当前组合是否合法
            int res = 0; // 当前组合的座位利用数
            
            // 遍历所有乘客
            for (int j = 0; ok && j < x; ++j) {
                // 检查第 j 位乘客是否选择乘坐
                if ((i >> j & 1) == 1) {
                    // 记录该乘客在上下车站点之间的乘客数量
                    for (int k = a.get(j).x; ok && k < a.get(j).y; ++k) {
                        ++cnt[k]; // 增加对应站点的乘客数量
                    }
                    // 计算当前乘客的座位利用数
                    res += a.get(j).y - a.get(j).x;
                }
            }

            // 检查是否有站点的乘客数量超过座位数
            for (int j = 0; j < n; ++j) {
                if (cnt[j] > m) { // 如果某个站点的乘客数量超过了座位数
                    ok = false; // 该组合不合法
                    break; // 退出循环
                }
            }

            // 如果组合合法，更新最大利用数
            if (ok) {
                ans = Math.max(ans, res); // 更新最大利用数
            }
        }
        
        System.out.println(ans); // 输出最大座位利用数
    }

    public static void main(String[] args) {
        solve(); // 调用解题函数
    }
}

C++

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

void solve() {
    int m, n, x;
    cin >> m >> n >> x; // 读取座位数、站点数和乘客数
    vector<PII> a(x); // 存储每个乘客的上下车站点
    for (int i = 0; i < x; ++i) {
        cin >> a[i].x >> a[i].y; // 读取乘客的上下车站点
    }
    
    int ans = 0; // 用于记录最大座位利用数
    for (int i = 0; i < (1 << x); ++i) { // 枚举所有可能的乘客组合
        vector<int> cnt(n, 0); // 记录每个站点的乘客数量
        bool ok = true; // 用于标记当前组合是否合法
        int res = 0; // 当前组合的座位利用数
        
        // 遍历所有乘客
        for (int j = 0; ok && j < x; ++j) {
            if (i >> j & 1) { // 如果第 j 位乘客选择乘坐
                // 记录该乘客在上下车站点之间的乘客数量
                for (int k = a[j].x; ok && k < a[j].y; ++k) {
                    ++cnt[k]; // 增加对应站点的乘客数量
                }
                res += a[j].y - a[j].x; // 计算当前乘客的座位利用数
            }
        }

        // 检查是否有站点的乘客数量超过座位数
        for (int j = 0; j < n; ++j) {
            if (cnt[j] > m) { // 超过座位数，不合法
                ok = false;
                break;
            }
        }

        // 更新最大利用数
        if (ok) ans = max(ans, res);
    }
    
    cout << ans << endl; // 输出最大座位利用数
}

signed main() {
    solve(); // 调用解题函数
}

Python

def solve():
    # 读取座位数、站点数和乘客数
    m, n, x = map(int, input().split())
    # 读取每位乘客的上下车站点，存储为元组列表
    a = [tuple(map(int, input().split())) for _ in range(x)]
    
    ans = 0  # 用于记录最大座位利用数
    
    # 枚举所有可能的乘客组合
    for i in range(1 << x):
        cnt = [0] * n  # 记录每个站点的乘客数量
        ok = True  # 用于标记当前组合是否合法
        res = 0  # 当前组合的座位利用数
        
        # 遍历所有乘客
        for j in range(x):
            # 检查第 j 位乘客是否选择乘坐
            if (i >> j) & 1:
                # 如果选择乘坐，更新对应站点的乘客数量
                for k in range(a[j][0], a[j][1]):
                    cnt[k] += 1
                # 计算当前乘客的座位利用数
                res += a[j][1] - a[j][0]

        # 检查是否有站点的乘客数量超过座位数
        for j in range(n):
            if cnt[j] > m:  # 如果某个站点的乘客数量超过了座位数
                ok = False  # 该组合不合法
                break  # 退出循环

        # 如果组合合法，更新最大利用数
        if ok:
            ans = max(ans, res)  # 更新最大利用数
            
    print(ans)  # 输出最大座位利用数

# 主程序入口
if __name__ == "__main__":
    solve()  # 调用解题函数

JS

const rl = require("readline").createInterface({ input: process.stdin  });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value; 
 
void (async function () {
    // 读取输入参数 m（座位数）、n（站点数）、x（乘客数）
    const [m, n, x] = (await readline()).split(' ').map(Number);
    
    // 存储所有乘客的行程区间 
    const passengers = [];
    for (let i = 0; i < x; i++) {
        const [s, e] = (await readline()).split(' ').map(Number);
        passengers.push({  s, e });
    }
 
    let maxUsage = 0; // 最大座位利用率 
    
    // 枚举所有可能的乘客组合（2^x种可能性）
    for (let mask = 0; mask < (1 << x); mask++) {
        const stationCounts = new Array(n).fill(0); // 每个站点的乘客计数 
        let isValid = true; // 当前组合是否合法 
        let currentUsage = 0; // 当前组合的座位利用率 
        
        // 遍历每个乘客，检查是否被选中 
        for (let i = 0; i < x && isValid; i++) {
            if (mask & (1 << i)) { // 若第i位乘客被选中 
                const { s, e } = passengers[i];
                // 更新区间计数器 
                for (let station = s; station < e; station++) {
                    if (++stationCounts[station] > m) {
                        isValid = false; // 超载则标记为非法 
                        break;
                    }
                }
                if (isValid) currentUsage += e - s; // 累加有效行程 
            }
        }
        
        // 最终全站检查（确保没有漏网之鱼）
        if (isValid) {
            for (let station = 0; station < n; station++) {
                if (stationCounts[station] > m) {
                    isValid = false;
                    break;
                }
            }
        }
        
        // 更新最大利用率 
        if (isValid) maxUsage = Math.max(maxUsage,  currentUsage);
    }
    
    console.log(maxUsage); 
})();

题目描述

一列具有 $m$ 个座位的火车，从起点到终点共停靠 $n$ 个站点，站点编号从$0$到$n-1$。发车前有$x$名乘客预定了座位，因为预定数量可能超出座位数，为了保证效率最大化，请计算如何分配才能是座位利用率最大，并输出最大的座位利用数。

说明:

座位利用数定义为每个座位被使用的站数。例如有两个座位，第一个座位从第$0$到$10$站有人坐(表示从$0$站上车，$10$站下车，第$10$站不占座，所以利用率是$10-0=10$)，第二个座位从第$1$到$9$站有人坐，则座位利用率为$(10-0)+(9-1)=18$。乘客在某站下车后，其他乘客从这一站就可以开始使用这个座位;无需考虑乘客需要更换座位的问题，保证任意时刻列车上乘客数量不超过$m$即可

输入描述

第一行输入$m、n$和$x$三个数字，分别表示列车座位数量、停靠站点数量和预定乘客数量

$1 <= m <= 9$

$2 <= n <= 20$

$1 <= x <= 9$

接下来$x$行输入，表示$x$条预定记录，每行有两个输入，分别表示此预定记录的上车站点和下车站点

输出描述

一个整数。

样例

输入

2 11 4
0 1
1 9
0 10
3 8

输出

19

说明

选择前三位乘客可以使座位利用率最大:$19=(1-0)+(9-1)+(10-0)$。若选择后两位乘客，则利用率为$15=(10-0)+(8-3)$。若选择全部四位乘客，则第$3$到$8$站车上存在$3$名乘客，超出列车座位数。

输入

1 11 2
0 5
5 10

输出

10