发红包问题的时间复杂度

122Ml

问题如下：
链接：https://ac.nowcoder.com/acm/contest/73762/B
来源：牛客网

在公司的年会上，有
N个人排着队准备毛红包，这些人按照从前到后的顺序排成一列，编号为1到N。
在活动期间，发生了Q次以下事件：
在时间Ti ，装有M i块钱的红包从空中飘下，站在队头的人得到该红包内的所有钱（如果队列中没有人，则没有人得到该红包）。然后，该人离开队列，并在时间T i+D i返回到原来的位置。

在所有Q次事件之后，请输出每个人获得的总金额数。

下面是我的代码，求大佬改进时间复杂度！

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. typedef long long ll;
   
4. 
   
5. int main() {
   
6.     ios::sync_with_stdio(0);
   
7.     cin.tie(0);
   
8. 
   
9.     long n, q;
   
10.     ll time, money, dtime;
    
11. 
    
12.     cin >> n >> q;
    
13. 
    
14.     vector<ll> m(n, 1), dp(n, 1), rmb(n, 0); // Using vectors instead of maps for better performance.
    
15. 
    
16.     for (ll i = 0; i < q; i++) {
    
17.         cin >> time >> money >> dtime;
    
18. 
    
19.         // Finding the first available position to perform the operation.
    
20.         for (ll j = 0; j < n; j++) {
    
21.             if (m[j] == 0) {
    
22.                 if (dp[j] == time) {
    
23.                     m[j] = 1;
    
24.                 }
    
25.                 else {
    
26.                     continue;
    
27.                 }
    
28.             }
    
29. 
    
30.             m[j] = 0;
    
31.             dp[j] = time + dtime;
    
32.             rmb[j] += money;
    
33. 
    
34.             break; // Break after finding the first available position.
    
35.         }
    
36.     }
    
37. 
    
38.     for (ll i = 0; i < n; i++) {
    
39.         cout << rmb[i] << '\n';
    
40.     }
    
41. 
    
42.     return 0;
    
43. }

复制代码

FishC

你的代码的时间复杂度是O(n*q)，其中n是人数，q是事件次数。因为在每次事件中，你都需要遍历所有人来找到第一个可用的位置进行操作。

我给你提供一个改进时间复杂度的思路：
1. 首先，我们需要记录每个人的当前位置和他们上一次返回的时间。
2. 然后，我们按照事件发生的时间顺序处理每个事件。对于每个事件，我们需要找到第一个可用的位置，并更新该人的位置和返回时间，并将红包金额加到该人的总金额中。
3. 为了寻找第一个可用的位置，我们可以使用一个队列来存储每个人。当有人收到红包离开队列时，我们将他们的位置和返回时间入队。
4. 在处理每个事件时，我们只需要检查队列头部的人是否可以参与当前事件。如果队列为空或队列头部的人无法参与当前事件（即他的返回时间晚于当前事件的发生时间），那么该事件就没有人能够参与，直接跳过。
5. 如果队列头部的人可以参与当前事件，我们将其位置和返回时间出队，并将红包金额加到该人的总金额中。然后，根据当前事件的发生时间和持续时间，计算该人下一次返回的时间，并将他的位置和返回时间入队。
6. 最后，我们遍历每个人，输出他们获得的总金额。

下面是一个改进时间复杂度的示例代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

struct Person {
    ll position;
    ll returnTime;
    ll totalMoney;

    Person(ll p, ll rt, ll tm) : position(p), returnTime(rt), totalMoney(tm) {}
};

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

    long n, q;
    ll time, money, dtime;

    cin >> n >> q;

    vector<Person> people;

    for (ll i = 0; i < q; i++) {
        cin >> time >> money >> dtime;

        // Check if the event has no one to receive the red packet
        if (people.empty() || people.front().returnTime > time) {
            continue;
        }

        Person p = people.front();
        people.pop();

        p.totalMoney += money;
        p.returnTime = time + dtime;

        people.push(p);
    }

    for (auto p : people) {
        cout << p.totalMoney << " ";
    }

    return 0;
}
这段代码的时间复杂度是O(q)，其中q是事件次数。我们将每个人的信息存储在一个队列中，按照事件发生的顺序进行处理。只有队列头部的人才能参与当前事件，这减少了不必要的遍历，提高了效率。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。