题解

题面描述

某云计算服务商为客户提供 $M$ 数量 GPU 核数的 GPU 分时租用服务，租用计费规则为：允许客户在每个时间单位按需租用不同的 GPU 核数，每个时间单位每个 GPU 核数的费用为 $R$ 。

现有 $N$ 个客户，每个客户有多个不重叠时间段租用一定数量的 GPU 核数的租用需求。对于有租用需求的客户，服务商可选择签约或不签约，若选择签约则需要满足其所有时间段中对 GPU 核数的需求。

为了实现租金最大化收益，服务商需在确保任意时间单位内分配的 GPU 核数总数不超过 $M$ 的基础上，选择与哪些客户签约租用协议。

请输出在租金最大化收益下的总租金。

若任意一个客户的需求都无法满足，则输出 $0$。

思路

1. 枚举签约方案：由于 $N\leq10$，可以对每个客户选择签约或不签约，枚举所有 $2^N$ 种可能的子集。
2. 验证可行性：对于每一个客户子集，将其所有时间段的需求汇总，检查在任意时间单位内的 GPU 核数总和是否超过 $M$。具体做法：
   • 收集所有时间段的开始和结束边界，进行离散化，得到有序的时间点数组。
   • 遍历相邻时间点区间，累加所有在该区间内客户的需求核数，若超过 $M$ 则该子集不可行。
3. 计算收益：若子集可行，计算总GPU*时间量 $W$： $W$ = $sum_{\text{客户}~i}$$sum_{[s,e]~\in~\mathrm{segments}_i}$($e-s+1$)$*$${needCores}$ 最终租金为 $W \times R$。
4. 取最大值：遍历所有子集，记录最大的 $W\times R$，即为答案。

复杂度：$O(2^N \times K \log K)$，其中 $K$ 为所有考虑中的时间段总数，符合题目约束。

C++

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

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

    // 读入 M, N, R
    ll M; int N; ll R;
    cin >> M >> N >> R;

    // 存储每个客户的时间段需求
    vector<vector<tuple<ll,ll,ll>>> segs(N);
    for (int i = 0; i < N; i++) {
        int t; cin >> t;
        while (t--) {
            ll s, e, c;
            char ch;
            cin >> s >> ch >> e >> ch >> c;  // 读入格式 s:e:c
            segs[i].emplace_back(s, e, c);
        }
    }

    ll ans = 0;
    // 枚举所有子集
    for (int mask = 0; mask < (1<<N); mask++) {
        vector<ll> xs;
        ll W = 0;
        // 收集边界
        for (int i = 0; i < N; i++) if (mask & (1<<i)) {
            for (auto &seg: segs[i]) {
                ll s,e,c; tie(s,e,c) = seg;
                xs.push_back(s);
                xs.push_back(e+1);
                W += (e - s + 1) * c;
            }
        }
        if (xs.empty()) continue;
        // 离散化
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        vector<ll> diff(xs.size()+1);
        // 差分数组构造
        for (int i = 0; i < N; i++) if (mask & (1<<i)) {
            for (auto &seg: segs[i]) {
                ll s,e,c; tie(s,e,c) = seg;
                int l = lower_bound(xs.begin(), xs.end(), s) - xs.begin();
                int r = lower_bound(xs.begin(), xs.end(), e+1) - xs.begin();
                diff[l] += c;
                diff[r] -= c;
            }
        }
        // 扫描检查容量
        ll cur = 0;
        bool ok = true;
        for (int i = 0; i+1 < (int)xs.size(); i++) {
            cur += diff[i];
            if (cur > M) { ok = false; break; }
        }
        if (ok) ans = max(ans, W * R);
    }

    cout << ans;
    return 0;
}

Python

import sys
from itertools import combinations

def read_input():
    # 读取所有输入并分割
    data = sys.stdin.read().split()
    M, N, R = map(int, data[:3])
    idx = 3
    segs = []
    for _ in range(N):
        t = int(data[idx]); idx += 1
        arr = []
        for _ in range(t):
            # 按格式 start:end:needCores
            s_str, e_str, c_str = data[idx].split(':')
            idx += 1
            s, e, c = int(s_str), int(e_str), int(c_str)
            arr.append((s, e, c))
        segs.append(arr)
    return M, N, R, segs


def is_subset_feasible(mask, N, M, segs):
    # 收集所有边界并构造差分
    xs = []
    W = 0
    for i in range(N):
        if mask & (1 << i):
            for s, e, c in segs[i]:
                xs.append(s)
                xs.append(e + 1)
                W += (e - s + 1) * c
    if not xs:
        return False, 0
    # 离散化
    xs = sorted(set(xs))
    diff = [0] * (len(xs) + 1)
    # 构造差分数组
    for i in range(N):
        if mask & (1 << i):
            for s, e, c in segs[i]:
                l = xs.index(s)
                r = xs.index(e + 1)
                diff[l] += c
                diff[r] -= c
    # 扫描区间可行性
    cur = 0
    for i in range(len(xs) - 1):
        cur += diff[i]
        if cur > M:
            return False, 0
    return True, W


def main():
    M, N, R, segs = read_input()
    ans = 0
    # 枚举所有子集
    for mask in range(1 << N):
        feasible, W = is_subset_feasible(mask, N, M, segs)
        if feasible:
            ans = max(ans, W * R)
    # 若所有子集都不行，ans 保持为 0
    print(ans)

if __name__ == '__main__':
    main()

Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long M = sc.nextLong();
        int N = sc.nextInt();
        long R = sc.nextLong();
        List<List<long[]>> segs = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int t = sc.nextInt();
            List<long[]> list = new ArrayList<>();
            for (int j = 0; j < t; j++) {
                String[] parts = sc.next().split(":");
                long s = Long.parseLong(parts[0]);
                long e = Long.parseLong(parts[1]);
                long c = Long.parseLong(parts[2]);
                list.add(new long[]{s, e, c});
            }
            segs.add(list);
        }
        long ans = 0;
        // 枚举子集
        for (int mask = 0; mask < (1<<N); mask++) {
            List<Long> xs = new ArrayList<>();
            long W = 0;
            for (int i = 0; i < N; i++) if ((mask & (1<<i)) != 0) {
                for (long[] seg: segs.get(i)) {
                    long s = seg[0], e = seg[1], c = seg[2];
                    xs.add(s);
                    xs.add(e + 1);
                    W += (e - s + 1) * c;
                }
            }
            if (xs.isEmpty()) continue;
            Collections.sort(xs);
            List<Long> uni = new ArrayList<>();
            for (long x: xs) if (uni.isEmpty() || uni.get(uni.size()-1) != x) uni.add(x);
            long[] diff = new long[uni.size()+1];
            for (int i = 0; i < N; i++) if ((mask & (1<<i)) != 0) {
                for (long[] seg: segs.get(i)) {
                    long s = seg[0], e = seg[1], c = seg[2];
                    int l = Collections.binarySearch(uni, s);
                    int r = Collections.binarySearch(uni, e+1);
                    diff[l] += c;
                    diff[r] -= c;
                }
            }
            long cur = 0;
            boolean ok = true;
            for (int i = 0; i+1 < uni.size(); i++) {
                cur += diff[i];
                if (cur > M) { ok = false; break; }
            }
            if (ok) ans = Math.max(ans, W * R);
        }
        System.out.println(ans);
    }
}

题目内容

某云计算服务商为客户提供 $M$ 数量 $GPU$ 核数的 $GPU$ 分时租用服务，租用计费规则为：允许客户在每个时间单位按需租用不同的 $GPU$ 核数，每个时间单位每个 $GPU$ 核数的费用为 $R$ 。

现有 $N$ 个客户，每个客户有多个不重叠时间段租用一定数量的 $GPU$ 核数的租用需求。对于有租用需求的客户，服务商可选择签约或不签约，若选择签约则需要满足租用需求中的所有时间段所需的 $GPU$ 核数。

为了实现租金最大化收益，服务商需在确保任意时间单位内分配的 $GPU$ 核数总数不超过 $M$ 的基础上，选择与哪些客户签约租用协议。

请输出租金最大化收益下的租金最大值。

输入描述

第一行为 $M、N、R$ 的数值，依次用空格隔开，输入格式为 $M$ $N$ $R$

从第二行开始，每行为一个客户的租用需求，共 $N$ 行。每行的9第一个数字为该客户端的时间段个数 $timeSegmentNum$ ，后续为 $timeSegmentNum$ 个时间段及所需的 $GPU$ 核数，时间段个数 $timeSegmentNum$ 与时间段之间、多个时间段之间均用空格分割。同一个客户多个时间段不会重叠。同一个客户多个时间段已按起始时间增序排序给出

每个时间段及所需的 $GPU$ 核数格式为 $star$ 起始时间编号：$end$ 结束时间编号：$needCores$ 该时间段所需的 $GPU$ 核数

变量取值范围

$1<=M<=100000$

$1<=N<=10$

$1<=R<=10$

$0<=start<=end<=10^9$

$1<=needCores<=10000$

$1<=timeSegmentNum<=100$

客户的租用需求样例 $2$ $0:0:1$ $3:6:10$ 的含义是共有 $2$ 个时间段，$0:0:1$ 表示在第 $0$ 个时间单位需要 $1$ 个 $GPU$ 核，$3:6:10$ 表示在从 $3$ 到 $6$ 的时间单位(包含 $3$ 和 $6$ )每个时间单位均需 $10$ 个$GPU$ 核

图例为：

输出描述

总租金最大值。

如果任意一个客户的需求都无法满足，则输出 $0$

样例1

输入

10 3 2
2 0:8:5 9:23:10
2 0:8:5 9:18:10
1 0:8:5

输出

480

说明

共 $3$ 个客户。

由于第一个客户和第二个客户在 $9:18$ 时间范围段内总核数为 $20$ 超过了 $10$ ，所以无法同时接受。

最大日租金方案为：接纳第一个客户和第三个客户的需求。

第一个客户共需要的 $GPU$ 核数为 $9*5+15*10=195$

第三个每户共需要的 $GPU$ 核数为 $9*5=45$

最大日租金值为 $(195+45)*2=480$

样例2

输入

10 2 1
1 0:3:6
1 3:10:6

输出

48

说明

最大 $GPU$ 核数为 $10$ ，共 $2$ 个客户。

第一个客户和第二个客户在 $3$ 时间点，总核数为 $12$ 超过了 $10$ ，所以无法同时接受。

第一个客户共需要的 $GPU$ 核数为 $4*6=24$

第二个客户共需要的 $GPU$ 核数为 $8*6=48$

为满足最大租金，采纳第二个客户，最大日租金值为 $48*1=48$

样例3

输入

10 1 1
1 0:5:20

输出

0

说明

最大 $GPU$ 核数为 $10$ ，共 $1$ 个客户。

在 $0$~$5$ 时间段需要 $20$ 个 $GPU$ 核数，无法满足。

输出 $0$