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

#define x first
#define y second
/**
 *
1 << 4 = 16，所以 i 从 0 到 15，总共有 16 种组合。每个 i 的二进制表示就是所有可能的组合情况：
i = 0: 0000 (没有乘客被选中)
i = 1: 0001 (选中乘客 0)
i = 2: 0010 (选中乘客 1)
i = 3: 0011 (选中乘客 0 和 1)
i = 4: 0100 (选中乘客 2)
i = 5: 0101 (选中乘客 0 和 2)
i = 6: 0110 (选中乘客 1 和 2)
i = 7: 0111 (选中乘客 0、1 和 2)
i = 8: 1000 (选中乘客 3)
i = 9: 1001 (选中乘客 0 和 3)
i = 10: 1010 (选中乘客 1 和 3)
i = 11: 1011 (选中乘客 0、1 和 3)
i = 12: 1100 (选中乘客 2 和 3)
i = 13: 1101 (选中乘客 0、2 和 3)
i = 14: 1110 (选中乘客 1、2 和 3)
i = 15: 1111 (选中所有乘客 0、1、2 和 3)
 */
int main()
{
    int m, n, x;
    cin >> m >> n >> x;
    vector<pair<int, int>> 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)// 枚举所有可能的乘客组合，1<<x表示2^x
    {
        vector<int> cnt(n, 0);//记录每一站有多少乘客在车上
        bool ok = true;// 判断当前组合是否满足条件
        int res = 0; // 记录当前组合的座位利用率
        for (int j = 0; ok && j < x; ++j) // 遍历每个乘客 x=4 j的范围是0-3 也就是
            if (i >> j & 1) // 检查当前组合是否选择了乘客j（即i的第j位是否为1）
            {
                for (int k = a[j].x; ok && k < a[j].y; ++k)// 如果选择了，更新cnt数组
                {
                    ++cnt[k];// 增加该乘客在每个站点占用座位的记录
                }
                res += a[j].y - a[j].x; // 累加该乘客的座位利用率
            }
        // 检查是否有站点的乘客数超过了座位数m
        for (int j = 0; j < n; ++j)
            if (cnt[j] > m) // 如果有超过的，标记组合无效
            {
                ok = false;
                break;
            }
        // 如果当前组合有效，更新最大座位利用率
        if (ok)
            ans = max(ans, res);
    }
    cout << ans << endl; // 输出最大座位利用率
}

n, m, x = map(int, input().split())
people_infos = []  # 存储乘客的上下车信息

# 定义一个函数来计算给定乘客选择的座位利用率
def calc(seq):
    seats = [set() for i in range(n)]  # 创建一个列表，包含 n 个集合，每个集合表示一个座位的使用情况
    result = 0  # 初始化座位利用数为 0
    select_peoples = [people_infos[i] for i, each in enumerate(seq) if each]  # 根据选择的序列筛选出实际乘客信息

    # 遍历每个选择的乘客
    for each_people in select_peoples:
        for i, seat in enumerate(seats):
            # 检查当前座位是否可以被此乘客使用
            if each_people[0] not in seat:  # 如果乘客的上车站点不在此座位的使用集合中
                # 将乘客的上下车区间加入到座位的使用集合中
                seat |= set(list(range(each_people[0], each_people[1])))  
                # 计算利用率，乘客的下车站点减去上车站点
                result += (each_people[1] - each_people[0])  
                break  # 找到一个可用座位后，跳出循环，处理下一个乘客
    return result  # 返回当前选择的座位利用数

# 读取每个乘客的上下车信息
for i in range(x):
    people_infos.append(list(map(int, input().split())))

people_infos.sort()  # 对乘客信息进行排序（可选，具体取决于需求）

max_num = 0  # 初始化最大座位利用数为 0

# 遍历所有可能的乘客选择组合（2^x 种组合）
for i in range(2 ** x):
    seqs = []  # 存储当前组合的选择情况
    for j in range(x):
        # 使用位运算判断第 j 个乘客是否被选择
        seqs.append(bool(i & (1 << j)))  
    # 计算当前选择组合的座位利用数，并更新最大值
    max_num = max(max_num, calc(seqs))  

print(max_num)

题面描述:

在一列具有$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()  # 调用解题函数