队列操作时间复杂度问题

122Ml

问题如下：

给定一个初始状态为空的序列，它将按顺序执行Q个操作
操作分为以下三种:
1 将a插入队列的末尾
2:查询队首元素，并将其删除。数据保证此时A非空
3:将队列升序排排序
输入描述:
第一行一个正整数Q(1 < Q < 2 x 10^5，表示操作数接下来Q行，每行表示一个操作
输出描述:
对于每个操作，输出一行一个正整数表示本次询问的答案。

求问大佬如何改进时间复杂度？

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. typedef long long ll;
   
5. 
   
6. using namespace std;
   
7. 
   
8. int main() {
   
9.     ios::sync_with_stdio(0);
   
10.     cin.tie(0);
    
11.     vector<ll> queue, dp;
    
12.     ll num, cnum = 0;
    
13.     ll temp,ans;
    
14.     bool bol=0,judge;
    
15.     cin >> num;
    
16. 
    
17.     for (ll i = 0; i < num; i++) {
    
18.         cin >> temp;
    
19. 
    
20.         if (temp == 1) {
    
21.             cin >> temp;
    
22.             queue.push_back(temp);
    
23.         }
    
24.         else if (temp == 2) {
    
25.             dp.push_back(queue.front());
    
26.             queue.erase(queue.begin());
    
27.             cnum += 1;
    
28.         }
    
29.         else if (temp == 3&&ans!=3) {
    
30.             sort(queue.begin(), queue.end());
    
31.         }
    
32.         ans = temp;
    
33.     }
    
34. 
    
35.     for (ll i = 0; i < cnum; i++) {
    
36.         cout << dp[i] << '\n';
    
37.     }
    
38. 
    
39.     return 0;
    
40. }

复制代码

FishC

这道题的关键是如何改进时间复杂度。目前的代码中，每次执行操作2时，都需要遍历整个队列来查询并删除队首元素，导致时间复杂度为O(n)，其中n表示当前队列的长度。而操作3中，每次都需要对整个队列进行排序，时间复杂度也是O(nlogn)。

我们可以使用两个队列来优化这个问题。一个队列用来保存原始的输入数据，另一个队列用来保存当前队列的有序状态。具体做法如下：

1. 当执行插入操作时，将元素插入到原始队列的末尾，并同时插入到有序队列的合适位置。
2. 当执行查询并删除队首元素操作时，直接从有序队列的队首获取即可，并从原始队列中删除。
3. 当执行排序操作时，不需要对整个队列进行排序，只需重新确定有序队列的元素顺序即可。

以下是改进后的代码：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. 
   
5. typedef long long ll;
   
6. 
   
7. using namespace std;
   
8. 
   
9. int main() {
   
10.     ios::sync_with_stdio(0);
    
11.     cin.tie(0);
    
12.    
    
13.     vector<int> originalQueue, sortedQueue;
    
14.     ll num, cnum = 0;
    
15.     ll temp, ans;
    
16.     bool bol = 0, judge;
    
17.     cin >> num;
    
18. 
    
19.     for (ll i = 0; i < num; i++) {
    
20.         cin >> temp;
    
21. 
    
22.         if (temp == 1) {
    
23.             cin >> temp;
    
24.             originalQueue.push_back(temp);
    
25.             
    
26.             // 将新插入的元素插入到有序队列的合适位置
    
27.             auto it = lower_bound(sortedQueue.begin(), sortedQueue.end(), temp);
    
28.             sortedQueue.insert(it, temp);
    
29.             
    
30.         } else if (temp == 2) {
    
31.             cout << sortedQueue.front() << endl;
    
32.             
    
33.             // 从原始队列和有序队列中删除队首元素
    
34.             originalQueue.erase(originalQueue.begin());
    
35.             sortedQueue.erase(sortedQueue.begin());
    
36.             
    
37.             cnum += 1;
    
38.             
    
39.         } else if (temp == 3 && ans != 3) {
    
40.             // 无需对整个队列进行排序，只需重新确定有序队列的元素顺序
    
41.             sort(sortedQueue.begin(), sortedQueue.end());
    
42.         }
    
43.         ans = temp;
    
44.     }
    
45. 
    
46.     for (ll i = 0; i < cnum; i++) {
    
47.         cout << sortedQueue[i] << endl;
    
48.     }
    
49.    
    
50.     return 0;
    
51. }

复制代码

这样做的话，每次执行操作2时只需要从有序队列的队首取出元素即可，时间复杂度为O(1)，而操作3的时间复杂度也为O(nlogn)，但是由于操作3不是连续执行的，所以整体的时间复杂度会得到极大的优化。

希望可以帮助到你！

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