招聘动态题解：队列模拟

题解：队列模拟

题解：队列模拟
1.数据结构存储
我们首先设计一个订单的数据结构，每个订单会包含以下信息：
uiduid：用户唯一标识。
typetype：请求类型（0表示订单请求，1表示助力请求）。
orderidorderid：订单唯一标识。
reqnumreqnum：订单请求的票数。
idxidx：订单请求在输入中的顺序编号。
其次，我们需要构建一个 订单位置映射表：使用哈希表olocoloc记录每个订单在ordersorders中的位置，方便快速定位订单。同时维护一个助力用户集合：使用哈希集合helperhelper记录已经参与助力的用户，确保每个用户只能助力一次。
2.输入数据处理
然后我们逐行读取每行输入，如果是订单请求（4个字段），将其解析为OrderOrder对象并加入ordersorders队列，同时更新olocoloc，如果是助力请求（3个字段），从以下几个方面检查助力请求是否有效：
条件1：目标订单是否存在。
条件2：助力用户是否重复助力。
条件3：助力是否过期（当前请求编号与目标订单编号差值不超过30）。
若助力有效，则将目标订单与前一个订单交换位置，并更新olocoloc。
3.订单处理
遍历ordersorders队列，依次处理每个订单请求：若当前订单的请求票数小于等于剩余票数remainremain，则该订单成功，减少剩余票数。否则，该订单失败。
C++
#include <bits/stdc++.h>
using namespace std;
struct Order {
    string uid;
    int type;
    string orderid;
    int reqnum;
    int idx;
};
int main() {
    int m;
    cin >> m;
    cin.ignore();  // 忽略多余的换行符
    string line;
    vector<Order> orders;
    unordered_map<string, int> oloc;
    unordered_set<string> helper;
    int cnt = 0;
    while (getline(cin, line) && cnt < 10000) {
        if (line.empty()) {
            continue;
        }
        cnt++;
        stringstream ss(line);
        string word;
        vector<string> tokens;
        while (ss >> word) {
            tokens.push_back(word);
        }
        // 当前是购票请求
        if (tokens.size() == 4) {
            Order o;
            o.uid = tokens[0];
            o.type = 0;
            o.orderid = tokens[2];
            o.reqnum = stoi(tokens[3]);
            o.idx = cnt;
            orders.push_back(o);
            oloc[o.orderid] = orders.size() - 1;
        } else if (tokens.size() == 3) {  // 当前是助力请求
            string helperuid = tokens[0];
            string helperoid = tokens[2];
            if (!oloc.count(helperoid)) {
                continue;
            }
            int loc = oloc[helperoid];
            Order& oo = orders[loc];
            // 不允许自己给自己助力，不允许重复助力
            if (helperuid == oo.uid || helper.count(helperuid)) {
                continue;
            }
            helper.insert(helperuid);
            // 过期助力，忽略
            if (cnt - oo.idx > 30) {
                continue;
            }
            if (loc == 0) {
                continue;
            }
            int prev = loc - 1;
            swap(orders[prev], orders[loc]);
            oloc[orders[prev].orderid] = prev;
            oloc[orders[loc].orderid] = loc;
        }
    }
    int remain = m, on = orders.size();

    for (int i = 0; i < on; i++) {
        cout << orders[i].uid << " " << orders[i].orderid << " "
             << orders[i].reqnum;
        if (orders[i].reqnum <= remain) {
            cout << " success" << endl;
            remain -= orders[i].reqnum;
        } else {
            cout << " failure" << endl;
        }
    }
    return 0;
}

Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m;  // 总余票数
        m = scanner.nextInt();  // 输入总余票数
        scanner.nextLine();  // 忽略多余的换行符

        // 定义结构体 Order，用于存储订单信息
        class Order {
            String uid;
            int type;
            String orderid;
            int reqnum;
            int idx;

            Order(String uid, int type, String orderid, int reqnum, int idx) {
                this.uid = uid;
                this.type = type;
                this.orderid = orderid;
                this.reqnum = reqnum;
                this.idx = idx;
            }
        }

        List<Order> orders = new ArrayList<>();  // 存储订单列表
        Map<String, Integer> oloc = new HashMap<>();  // 存储订单ID到订单索引的映射
        Set<String> helper = new HashSet<>();  // 存储已经助力的用户ID
        int cnt = 0;  // 当前处理的请求总数

        // 循环读取每一行输入，直到遇到空行或请求总数达到 10000
        while (scanner.hasNextLine() && cnt < 10000) {
            String line = scanner.nextLine();
            if (line.isEmpty()) {
                continue;
            }
            cnt++;
            Scanner lineScanner = new Scanner(line);
            List<String> tokens = new ArrayList<>();
            while (lineScanner.hasNext()) {
                tokens.add(lineScanner.next());
            }
            lineScanner.close();

            // 当前是购票请求
            if (tokens.size() == 4) {
                Order o = new Order(tokens.get(0), 0, tokens.get(2), Integer.parseInt(tokens.get(3)), cnt);
                orders.add(o);
                oloc.put(o.orderid, orders.size() - 1);
            } else if (tokens.size() == 3) {  // 当前是助力请求
                String helperuid = tokens.get(0);
                String helperoid = tokens.get(2);
                if (!oloc.containsKey(helperoid)) {
                    continue;
                }
                int loc = oloc.get(helperoid);
                Order oo = orders.get(loc);
                // 不允许自己给自己助力，不允许重复助力
                if (helperuid.equals(oo.uid) || helper.contains(helperuid)) {
                    continue;
                }
                helper.add(helperuid);
                // 过期助力，忽略
                if (cnt - oo.idx > 30) {
                    continue;
                }
                if (loc == 0) {
                    continue;
                }
                int prev = loc - 1;
                // 交换订单位置
                Collections.swap(orders, prev, loc);
                oloc.put(orders.get(prev).orderid, prev);
                oloc.put(orders.get(loc).orderid, loc);
            }
        }

        int remain = m, on = orders.size();  // 当前剩余票数和订单数量

        // 按调整后的排队顺序依次处理每个订单请求
        for (int i = 0; i < on; i++) {
            System.out.print(orders.get(i).uid + " " + orders.get(i).orderid + " " + orders.get(i).reqnum);
            if (orders.get(i).reqnum <= remain) {
                System.out.println(" success");
                remain -= orders.get(i).reqnum;  // 更新剩余票数
            } else {
                System.out.println(" failure");  // 输出请求失败信息
            }
        }
        scanner.close();
    }
}

Python
# 定义结构体 Order，用于存储订单信息
class Order:
    def __init__(self, uid, type, orderid, reqnum, idx):
        self.uid = uid
        self.type = type
        self.orderid = orderid
        self.reqnum = reqnum
        self.idx = idx

# 读取总余票数
m = int(input().strip())

# 存储订单列表
orders = []
# 存储订单ID到订单索引的映射
oloc = {}
# 存储已经助力的用户ID
helper = set()
cnt = 0  # 当前处理的请求总数

# 循环读取每一行输入，直到遇到空行或请求总数达到 10000
try:
    while True:
        line = input().strip()
        if line == "":
            break
        cnt += 1
        if cnt > 10000:
            continue
        tokens = line.split()

        # 当前是购票请求
        if len(tokens) == 4:
            o = Order(tokens[0], 0, tokens[2], int(tokens[3]), cnt)
            orders.append(o)
            oloc[o.orderid] = len(orders) - 1
        elif len(tokens) == 3:  # 当前是助力请求
            helperuid = tokens[0]
            helperoid = tokens[2]
            if helperoid not in oloc:
                continue
            loc = oloc[helperoid]
            oo = orders[loc]
            # 不允许自己给自己助力，不允许重复助力
            if helperuid == oo.uid or helperuid in helper:
                continue
            helper.add(helperuid)
            # 过期助力，忽略
            if cnt - oo.idx > 30:
                continue
            if loc == 0:
                continue
            prev = loc - 1
            # 交换订单位置
            orders[prev], orders[loc] = orders[loc], orders[prev]
            oloc[orders[prev].orderid] = prev
            oloc[orders[loc].orderid] = loc
except EOFError:
    pass  # 处理输入结束的情况

remain = m  # 当前剩余票数
on = len(orders)  # 订单数量

# 按调整后的排队顺序依次处理每个订单请求
for i in range(on):
    print(f"{orders[i].uid} {orders[i].orderid} {orders[i].reqnum}", end=" ")
    if orders[i].reqnum <= remain:
        print("success")
        remain -= orders[i].reqnum  # 更新剩余票数
    else:
        print("failure")  # 输出请求失败信息
相关面经
全部面经
招聘动态
更多动态