2024.9.11-秋招-第3题-基站的盈利问题

0

kongyuoy LV 1 @ 2024-10-28 13:51:50

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{   
    int n,m;
    cin>>n>>m;
    vector<vector<int>> logs(m,vector<int>(3,0));
    for(int i=0;i<m;++i) for(int j=0;j<3;++j) cin>>logs[i][j];
    // for(int i=0;i<m;++i) for(int j=0;j<3;++j) cout<<logs[i][j];

    vector<int> dp(m,0);
    // 前对齐 + 遍历业务 -> 时间复杂度为O(m^2) -> 10^10 > 10^8 会超时,方法可行（已验证）
    // sort(logs.begin(),logs.end(),[](const vector<int>& a, const vector<int>& b){return a[0]<b[0];});
    // for(int i=0;i<m;++i)
    // {
    //     dp[i] = logs[i][2];
    //     for(int j=0;j<i;++j)
    //     {
    //         if(logs[i][0]>logs[j][1]) dp[i] = max(dp[i],dp[j]+logs[i][2]);
    //     }
    // }
    // cout << *max_element(dp.begin(),dp.end());

    // 优化，二分查找，找到合格的业务 ->时间复杂度O(mlogsm) -> 10^6 不会超时,注意此处排序是按照结束时间进行排序！
    sort(logs.begin(), logs.end(), [](const vector<int> &a, const vector<int> &b){return a[1]<b[1];});
    for (int i = 0; i < m; i++) dp[i] = logs[i][2];
    for (int i = 1; i < m; i++) 
    {
        auto idx = upper_bound(logs.begin(), logs.begin() + i, logs[i][0]-1, [](int startTime, const vector<int> &log)->bool{return log[1]>startTime;}) - logs.begin();
        //根据LeetCode 1235题改，logs[i][0]-1 将大于等于改成了大于
        if (idx - 1 >= 0) dp[i] = max({dp[i], dp[i - 1], dp[idx - 1] + logs[i][2]});//只选当前业务/不选当前业务/选之前业务+当前业务
        else dp[i] = max(dp[i], dp[i - 1]);
    }
    cout<<dp.back();

    return 0;
}

0

kongyuoy LV 1 @ 2024-10-28 11:49:02

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int main()
{
    // 收集头部 + 遍历基站 O(m+n) 空间复杂度O(m)
    int n;
    int m;
    cin>>n>>m;
    cin.get();
    unordered_map<int,vector<pair<int,int>>> businesses;
    int l,r,x;
    for(int i=0;i<m;++i)
    {
        cin >> l >> r >> x;
        businesses[l].push_back({r,x});
    }
    vector<int> dp(n+2,0);
    dp[n+1] = 0;
    for(int i=n;i>=1;--i)
    {
        dp[i] = dp[i+1];
        for(const pair<int,int>& li:businesses[i])
        {
            dp[i] = max(dp[i], dp[li.first+1]+li.second);
        }      
    }
    // cout<<sizeof(businesses)<<endl;
    cout<<dp[1];
    return 0;
}

0

kongyuoy LV 1 @ 2024-10-28 11:42:22

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int main()
{
    // 收集尾部 + 遍历基站 O(m+n) 空间复杂度O(m)
    int n;
    int m;
    cin>>n>>m;
    cin.get();
    unordered_map<int,vector<pair<int,int>>> businesses;
    int l,r,x;
    for(int i=0;i<m;++i)
    {
        cin >> l >> r >> x;
        businesses[r].push_back({l,x});
    }
    vector<int> dp(n+1,0);
    dp[0] = 0;
    for(int i=1;i<n+1;++i)
    {
        dp[i] = dp[i-1];
        for(const pair<int,int>& ri:businesses[i])
        {
            dp[i] = max(dp[i], dp[ri.first-1]+ri.second);
        }      
    }
    // cout<<sizeof(businesses)<<endl;
    cout<<dp[n];
    return 0;
}

0

kongyuoy LV 1 @ 2024-10-28 11:37:02

#include<iostream>
#include <new>
#include<vector>

using namespace std;

int main()
{
    // 收集尾部 + 遍历基站 O(m+n) 空间复杂度O(m的上限)
    int n;
    int m;
    cin>>n>>m;
    cin.get();
    int maxn = 100000;
    vector<pair<int,int>> businesses[maxn]; //空间换时间
    int l,r,x;
    for(int i=0;i<m;++i)
    {
        cin >> l >> r >> x;
        businesses[r].emplace_back(make_pair(l,x));
    }
    vector<int> dp(n+1,0);
    dp[0] = 0;
    for(int i=1;i<n+1;++i)
    {
        dp[i] = dp[i-1];
        for(const pair<int,int>& ri:businesses[i])
        {
            dp[i] = max(dp[i], dp[ri.first-1]+ri.second);
        }      
    }
    // cout<<sizeof(businesses)<<endl;
    cout<<dp[n];
    return 0;
}

0

kongyuoy LV 1 @ 2024-10-27 21:33:29

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class mycompare
{
public:
    bool operator()(const vector<int>& a, const vector<int>& b)
    {
        return a[0] < b[0];
    }
};
int main()
{   
    int n,m;
    cin>>n>>m;
    vector<vector<int>> log(m,vector<int>(3,0));
    for(int i=0;i<m;++i) for(int j=0;j<3;++j) cin>>log[i][j];
    // for(int i=0;i<m;++i) for(int j=0;j<3;++j) cout<<log[i][j];
    sort(log.begin(),log.end(),mycompare());
    vector<int> dp(m,0);
    //前对齐 + 遍历业务 -> 时间复杂度为O(m^2) -> 10^10 > 10^8 会超时
    for(int i=0;i<m;++i)
    {
        dp[i] = log[i][2];
        for(int j=0;j<i;++j)
        {
            if(log[i][0]>log[j][1])
            {
                dp[i] = max(dp[i],dp[j]+log[i][2]);
            }
        }
    }
    cout << *max_element(dp.begin(),dp.end());
    return 0;
}

0

TaZi SU @ 2024-9-11 20:21:21

题面解释:

在一个基站链式组网中，有 $N$ 个基站，按照从左到右的顺序编号。现有多个“业务”需求，每个业务用三元组表示：起始基站编号、结束基站编号和利润。基站只能被一个业务占用，所选业务集合必须保证没有基站重复使用。目标是选择一组业务，使得总利润最大化。输入包含两个整数 $N$ （基站数量，范围 $[1, 10000]$ ）和 $M$ （业务数量，范围 $[1, 100000]$ ），接下来是 $M$ 行，每行三个整数 $K1$ 、 $K2$ 和 $R$ ，表示起始基站编号、结束基站编号和利润，其中 $K1, K2 < N$ 且 $K1 < K2$ ，利润 $R$ 的范围为 $[1, 100]$ 。输出一个整数，表示能够获得的最大利润。

思路：动态规划

本题为LeetCode原题:1235. 规划兼职工作的化简版

对于处于位置 $K2$ 处的一个可选基站，其占据位置为 $[K1,K2]$ ，利润为 $R$ 。那么如果要选择该基站，上一个基站必须处于 $K2$ 之前。

定义 $f[i]$ 表示终点在 $i$ 及以前的所有基站所能获得的最大利润，有：

$f[i]=max\{f[i-1],f[K1_j-1]+R_j\}$ 。

其中 $K2_j==i$ 。

动态规划思路

我们定义一个动态规划数组 $f[i]$ ，表示以基站 $i$ 为终点的所有业务所能获得的最大利润。根据题意，状态转移方程可以表示为：

f[i] = \max\{f[i-1], f[K1_j-1] + R_j\}

其中 $K2_j == i$ ，即终点为 $i$ 的所有业务， $K1_j$ 是该业务的起始基站编号， $R_j$ 是该业务的利润。这个公式的含义是，我们在计算基站 $i$ 的最大利润时，有两个选择：要么不选择终点为 $i$ 的业务，这样利润就是 $f[i-1]$ ；要么选择终点为 $i$ 的某个业务，这时我们需要查看其起始位置的最大利润（即 $f[K1_j-1]$ ）加上当前业务的利润 $R_j$ 。

实现步骤

输入处理：
- 首先读取基站数量 $N$ 和业务数量 $M$ 。
- 使用一个数组 a 来存储每个基站终点为 $i$ 的所有业务信息，包括起始位置和利润。
动态规划计算：
- 初始化动态规划数组 $f$ ，对于每个基站 $i$ ，初始值为 $f[i-1]$ ，表示不选择任何终点为 $i$ 的业务。
- 遍历所有终点为 $i$ 的业务，更新最大利润值。
- 通过 max 函数更新 $f[i]$ 的值。
输出结果：
- 最终， $f[n]$ 就是以第 $N$ 个基站为终点的所有业务所能获得的最大利润。

代码

C++

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

const int maxn=1e4+10;  // 定义最大可处理的基站数量
int n, m;  // n表示最大基站位置，m表示基站数量
vector<pair<int, int>> a[maxn];  // 用于存储每个终点位置的基站信息 (起点, 利润)
int f[maxn];  // 动态规划数组，存储终点为i的最大利润

int main() {
    cin >> n >> m;  // 输入n和m
    for (int i = 1; i <= m; ++i) {
        int l, r, c;  // l为基站起点，r为终点，c为利润
        cin >> l >> r >> c;  // 输入基站信息
        a[r].push_back(make_pair(l, c));  // 按照终点r将基站信息存入a[r]
    }
    
    // 动态规划计算
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1];  // 不选择终点为i的基站，继承f[i-1]
        for (auto x : a[i]) {  // 遍历所有终点为i的基站
            f[i] = max(f[i], f[x.first - 1] + x.second);  // 更新最大利润
        }
    }
    
    cout << f[n];  // 输出n位置的最大利润
    return 0;
}

python

n = int(input())  # 输入n，表示最大基站位置
m = int(input())  # 输入m，表示基站数量
arr = [list(map(int, input().split())) for _ in range(m)]  # 输入每个基站的起点、终点和利润
arr.sort(key=lambda x: x[1])  # 按照基站的终点位置排序
g = [-1] * (n + 1)  # 动态规划数组，初始化为-1，表示未计算状态
g[0] = 0  # 基础状态，终点为0时，利润为0
now = 0  # 当前处理到的基站索引

# 动态规划计算
for i in range(1, n + 1):
    g[i] = g[i - 1]  # 不选择终点为i的基站，继承g[i-1]
    while now < m and arr[now][1] == i:  # 遍历所有终点为i的基站
        x, y, v = arr[now]  # 读取基站的起点x，终点y，利润v
        now += 1  # 处理下一个基站
        g[y] = max(g[y], g[x - 1] + v)  # 更新最大利润

print(g[n])  # 输出n位置的最大利润

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 输入最大基站位置n
        int m = sc.nextInt(); // 输入基站数量m
        
        int[][] arr = new int[m][3]; // 用于存储每个基站的起点、终点和利润
        
        // 读取基站信息
        for (int i = 0; i < m; i++) {
            arr[i][0] = sc.nextInt(); // 读取基站的起点
            arr[i][1] = sc.nextInt(); // 读取基站的终点
            arr[i][2] = sc.nextInt(); // 读取基站的利润
        }
        
        // 按照终点对基站进行排序
        Arrays.sort(arr, (a, b) -> Integer.compare(a[1], b[1]));
        
        int[] g = new int[n + 1]; // 动态规划数组，存储到达每个位置的最大利润
        Arrays.fill(g, -1); // 初始化为-1，表示未处理的状态
        g[0] = 0; // 基础状态，终点为0时，利润为0

        int now = 0; // 当前处理的基站索引
        // 动态规划计算
        for (int i = 1; i <= n; i++) {
            g[i] = g[i - 1]; // 不选择终点为i的基站，继承g[i-1]
            while (now < m && arr[now][1] == i) { // 遍历所有终点为i的基站
                int x = arr[now][0]; // 基站起点
                int y = arr[now][1]; // 基站终点
                int v = arr[now][2]; // 基站利润
                now++; // 处理下一个基站
                g[y] = Math.max(g[y], g[x - 1] + v); // 更新最大利润
            }
        }
        
        System.out.println(g[n]); // 输出n位置的最大利润
        sc.close();
    }
}

6 solutions

题面解释:

思路：动态规划

本题为LeetCode原题:1235. 规划兼职工作的化简版

动态规划思路

实现步骤

代码

C++

python

java

Information

Status

Development

Support

6 solutions

题面解释:

思路：动态规划

本题为LeetCode原题:1235. 规划兼职工作的化简版

动态规划思路

实现步骤

代码

C++

python

java

2024.9.11-秋招-第3题-基站的盈利问题

Information

Status

Development

Support

SIGN IN