给我一道luogu题,用到简单的优先队列
时间: 2024-10-11 10:07:03 浏览: 4
在洛谷(Luogu)上有许多练习题涉及到简单优先队列(如`std::priority_queue`),这里提供一个基础的题目作为例子:
**题目链接**: [1067. 最长上升子序列 (Medium) - 洛谷](https://www.luogu.com.cn/problem/P1067)
**题目描述**:
给定一个无序整数数组 nums,找到最长递增子序列的长度。你可以假设输入一定是有效的。
**解决方案**:
这道题目可以使用动态规划结合优先队列来解决。首先创建一个空的优先队列(堆),然后遍历数组。对于每个元素,如果它大于当前堆顶元素,则将其加入队列并更新答案;如果不大于,就直接跳过。堆保证了取出的是当前队列中最小的元素,因此时间复杂度为O(n log n),其中n是数组的长度。
```cpp
#include <iostream>
#include <queue>
using namespace std;
int longestIncreasingSubsequence(vector<int>& nums) {
if (nums.empty()) return 0;
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(nums[0]);
int ans = 1;
for (int i = 1; i < nums.size(); ++i) {
if (pq.top() < nums[i]) {
pq.pop();
pq.push(nums[i]);
ans++;
}
}
return ans;
}
int main() {
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
cout << longestIncreasingSubsequence(nums) << endl;
return 0;
}
```