发红包问题的时间复杂度
问题如下：链接：https://ac.nowcoder.com/acm/contest/73762/B
来源：牛客网
在公司的年会上，有
N个人排着队准备毛红包，这些人按照从前到后的顺序排成一列，编号为1到N。
在活动期间，发生了Q次以下事件：
在时间Ti ，装有M i块钱的红包从空中飘下，站在队头的人得到该红包内的所有钱（如果队列中没有人，则没有人得到该红包）。然后，该人离开队列，并在时间T i+D i返回到原来的位置。
在所有Q次事件之后，请输出每个人获得的总金额数。
下面是我的代码，求大佬改进时间复杂度！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long n, q;
ll time, money, dtime;
cin >> n >> q;
vector<ll> m(n, 1), dp(n, 1), rmb(n, 0); // Using vectors instead of maps for better performance.
for (ll i = 0; i < q; i++) {
cin >> time >> money >> dtime;
// Finding the first available position to perform the operation.
for (ll j = 0; j < n; j++) {
if (m == 0) {
if (dp == time) {
m = 1;
}
else {
continue;
}
}
m = 0;
dp = time + dtime;
rmb += money;
break; // Break after finding the first available position.
}
}
for (ll i = 0; i < n; i++) {
cout << rmb << '\n';
}
return 0;
} 你的代码的时间复杂度是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 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]