这是一个典型的贪心算法问题 - 活动选择问题。可以使用贪心算法来解决,具体步骤如下:

  1. 根据输入的外卖订单信息,按照下单时刻 'si' 的非降序对订单进行排序。同时,记录每个订单的下单时刻、往返时间和酬劳。
  2. 初始化一个变量 'current_time' 为 0,表示当前时间。
  3. 初始化一个变量 'total_reward' 为 0,表示当前已赚取的酬劳总和。
  4. 遍历排序后的订单列表:
    • 如果当前订单的下单时刻 'si' 大于等于 'current_time',则接受这个订单。
      • 更新 'current_time' 为当前订单的下单时刻 'si' 加上往返时间 'ti',表示小明送完这个订单后的时间。
      • 更新 'total_reward' 为当前已赚取的酬劳总和加上当前订单的酬劳 'ai'。
  5. 返回 'total_reward',即小明可以赚取的最大酬劳。

根据输入描述,可以按照以下方式读取输入数据,并使用贪心算法求解:

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

struct Order {
    int s;
    int t;
    int a;
};

bool compareOrders(const Order& o1, const Order& o2) {
    return o1.s < o2.s;
}

int main() {
    int n;
    cin >> n;
    
    vector<Order> orders(n);
    for (int i = 0; i < n; i++) {
        cin >> orders[i].s;
    }
    for (int i = 0; i < n; i++) {
        cin >> orders[i].t;
    }
    for (int i = 0; i < n; i++) {
        cin >> orders[i].a;
    }
    
    sort(orders.begin(), orders.end(), compareOrders);
    
    int current_time = 0;
    int total_reward = 0;
    
    for (int i = 0; i < n; i++) {
        if (orders[i].s >= current_time) {
            current_time = orders[i].s + orders[i].t;
            total_reward += orders[i].a;
        }
    }
    
    cout << total_reward << endl;
    
    return 0;
}

这样,输出结果就是小明在今天可以赚取的最大酬劳。

外卖员接单最优策略:贪心算法求解最大收益

原文地址: https://www.cveoy.top/t/topic/ljO 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录