题解

题目描述

肯德基店销售炸鸡、薯条、可乐三种实物，准备三种食物的速度一样，且三种食物同时制作。每个订单由三部分组成，分别表示炸鸡、薯条、可乐的需求份数。每个订单的食物需求是固定的，而订单的准备时间取决于这些食物的需求量。要求根据食物的准备情况，计算出 N 个订单的取餐顺序。

输入描述

输入由一串连续的数字组成，表示多个订单的需求，格式为：每个订单的炸鸡、薯条、可乐需求份数依次排列。数组的长度是订单数的三倍，每三个数字代表一个订单的需求。

输出描述

输出一个以空格隔开的数组，数组的长度为订单的数量，每个元素为订单的编号，表示订单取餐的顺序。如果多个订单的食物需求相同，则按订单号从小到大排序输出。

示例

示例 1

输入

0 0 1 0 1 0 1 0 0

输出

0 1 2

说明
有三个订单，第一个订单：0份炸鸡，0份薯条，1份可乐；第二个订单：0份炸鸡，1份薯条，0份可乐；第三个订单：1份炸鸡，0份薯条，0份可乐。
订单的取餐顺序为：0, 1, 2。
第一次，准备1份炸鸡、1份薯条、1份可乐，三个订单都可以同时取餐。

示例 2

输入

1 1 3 0 1 0 1 0 0

输出

1 2 0

说明
有三个订单，第一个订单：1份炸鸡，1份薯条，3份可乐；第二个订单：0份炸鸡，0份薯条，1份可乐；第三个订单：0份炸鸡，0份薯条，1份可乐。
订单的取餐顺序为：1, 2, 0。
第一步，准备1份炸鸡、1份薯条、1份可乐，第一个订单没有准备好；
第二步，准备1份炸鸡、1份薯条、1份可乐，第二个和第三个订单可以取餐；
第三步，准备0份炸鸡、0份薯条、1份可乐，第三个订单可以取餐。

解题思路

思路解析

1. 订单格式化：首先将输入数据解析成一个订单列表，每个订单包含三项内容：炸鸡、薯条和可乐的份数，以及其对应的订单编号。

2. 排序策略：因为每次取餐需要同时准备三种食物，因此，我们的目标是找出在某一时刻能够同时准备并分发的所有订单。
   为了简化问题，可以通过将每个订单的需求排序的方式来确定取餐顺序。每个订单的总需求量（炸鸡、薯条和可乐的最大需求量）决定了这个订单何时能取餐，因此我们可以通过排序来确定取餐的顺序。

3. 模拟取餐过程：假设每次将订单中的三种食物份数累计，然后依次发放。每次准备好某种食物后，检查哪些订单可以取餐，并按照订单号顺序输出。

4. 解决步骤：

   • 将输入的订单数据分割成每个订单的食物需求。
   • 对订单进行排序：首先按照订单的需求量进行排序，需求相同的订单按订单编号排序。
   • 输出排序后的订单编号。

Python代码实现

def solve_orders(order_data):
    # 计算订单数量 N
    N = len(order_data) // 3
    orders = []
    
    # 将订单数据转化为每个订单的食物需求元组：(炸鸡, 薯条, 可乐, 订单号)
    for i in range(N):
        chicken, fries, cola = order_data[i*3], order_data[i*3+1], order_data[i*3+2]
        orders.append((chicken, fries, cola, i))
    
    # 按照每个订单的三种食物需求的最大值进行升序排序
    orders.sort(key=lambda x: (max(x[0], x[1], x[2]), x[3]))

    # 输出排序后的订单号
    return [order[3] for order in orders]

# 输入数据
order_data = list(map(int, input().split()))

# 输出结果
result = solve_orders(order_data)
print(" ".join(map(str, result)))

Java代码实现

import java.util.*;

public class Main {
    public static int[] solveOrders(int[] orderData) {
        int N = orderData.length / 3;
        List<int[]> orders = new ArrayList<>();
        
        // 将订单数据转化为每个订单的食物需求及订单号
        for (int i = 0; i < N; i++) {
            int chicken = orderData[i * 3];
            int fries = orderData[i * 3 + 1];
            int cola = orderData[i * 3 + 2];
            orders.add(new int[]{chicken, fries, cola, i});
        }
        
        // 按照需求的最大值和订单号排序
        orders.sort((o1, o2) -> {
            int max1 = Math.max(Math.max(o1[0], o1[1]), o1[2]);
            int max2 = Math.max(Math.max(o2[0], o2[1]), o2[2]);
            return max1 == max2 ? Integer.compare(o1[3], o2[3]) : Integer.compare(max1, max2);
        });

        // 结果数组
        int[] result = new int[N];
        for (int i = 0; i < N; i++) {
            result[i] = orders.get(i)[3];
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        int[] orderData = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            orderData[i] = Integer.parseInt(input[i]);
        }

        int[] result = solveOrders(orderData);
        for (int order : result) {
            System.out.print(order + " ");
        }
    }
}

C++代码实现

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

vector<int> solveOrders(vector<int>& orderData) {
    int N = orderData.size() / 3;  // 计算订单数量
    vector<array<int, 3>> orders;  // 用来存储每个订单的三种食物需求量
    
    // 填充订单数据
    for (int i = 0; i < N; i++) {
        int chicken = orderData[i * 3];
        int fries = orderData[i * 3 + 1];
        int cola = orderData[i * 3 + 2];
        orders.push_back({chicken, fries, cola});  // 每个订单为一个array<int, 3>
    }

    // 使用 lambda 表达式进行排序：按照最大需求量升序排序，若相同则按订单号升序
    vector<int> indices(N);
    iota(indices.begin(), indices.end(), 0);  // 初始化订单号数组
    
    // 排序：首先比较三种食物的最大值，若相同则按订单号升序
    sort(indices.begin(), indices.end(), [&orders](int a, int b) {
        int maxA = max({orders[a][0], orders[a][1], orders[a][2]});
        int maxB = max({orders[b][0], orders[b][1], orders[b][2]});
        return maxA == maxB ? a < b : maxA < maxB;  // 改为升序排序
    });

    return indices;  // 返回排序后的订单号
}

int main() {
    string line;
    getline(cin, line);  // 读取输入
    stringstream ss(line);
    vector<int> orderData;
    int num;

    // 解析输入数据
    while (ss >> num) {
        orderData.push_back(num);
    }

    // 获取排序后的订单号
    vector<int> result = solveOrders(orderData);
    
    // 输出结果
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i != result.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}

警告：本题目有歧义，题解仅供参考

题目内容

肯德基店销售炸鸡、薯条、可乐三种实物，准备三种食物的速度一样，且三种食物同时制作;三种食物同时制作，按订单顺序进行分发食物。现在有 $N$ 个订单，每个订单用连续三位数组元素表示，数组的元素是对应食物的份数。$N$ 最大为 $100$ 万，每个订单里每份食物最多 $100$ 万份。请计算 $N$ 个订单的取餐顺序，如果多个订单可以同时取餐，按订单号从小到大排序输出。

输入描述

一个以空格隔开的数组，数组长度为订单个数的 $3$ 倍。

格式：订单 $0$ 的炸鸡份数 订单 $0$ 的薯条份数 订单 $0$ 的可乐份数 订单 $1$ 的炸鸡份数 订单 $1$ 的薯条份数 订单 $1$ 的可乐份数

输出描述

一个以空格隔开的数组，数组长度为订单个数，元素为订单号。

样例1

输入

0 0 1 0 1 0 1 0 0

输出

0 1 2

说明

1、有三个订单，第一个订单: $0$ 份炸鸡，$0$ 份薯条，$1$ 份可乐;第二个订单:$0$ 份炸鸡，$1$ 份薯条，$0$ 份可乐;第三个订单: $1$ 份炸鸡，$0$ 份薯条，$0$ 份可乐。订单的叫号顺序为:$0,1,2$

2、计算步骤:第一步，准备 $1$ 份炸鸡，$1$ 份薯条，$1$ 份可乐，三个订单都可以取餐。

样例2

输入

1 1 3 0 1 0 1 0 0

输出

1 2 0

说明

1、有三个订单，第一个订单:$1$ 份炸鸡，$1$ 份薯条，$3$ 份可乐;第二个订单:$0$ 份炸鸡，$0$ 份薯条，$1$ 份可乐;第三个订单:$0$ 份炸鸡，$0$ 份薯条，$1$ 份可乐。订单的叫号顺序为: $1,2,0$

2、计算步骤:第一步，准备 $1$ 份炸鸡，$1$ 份薯条，$1$ 份可乐，第一个订单未准备好;第二步，准备 $1$ 份炸鸡，$1$ 份薯条，$1$ 份可乐，第二个和三个订单可以取餐;第三步，准备 $0$ 份炸鸡，$0$ 份薯条，$1$ 份可乐，第一个订单取餐。