文章目錄

• • 1. 題目鏈接
  • 2. 題目解讀
  • 3. 代碼
  • • 3.1 Runtime Error 代碼

1. 題目鏈接

http://poj.org/problem?id=1442

2. 題目解讀

可以利用大小堆，大堆長度從1開始，每次+1
大堆元素都比小堆的小，那么大堆頂的元素就是第k小的元素

3. 代碼

3.1 Runtime Error 代碼

本地運行示例，結果一致，poj提交RE，還沒解決

/*** @description: 用大小堆求解* @author: michael ming* @date: 2019/5/31 23:21* @modified by: */ #include <iostream> #include <algorithm> #include <vector> #include <functional> using namespace std; int arr[30005], total[30005]; int main() {int arrlen, k, arrindex=1, maxheapsize=0, insertnum , minheapsize;cin >> arrlen >> k;for(int i = 1; i <= arrlen; ++i)cin >> arr[i];for(int i = 1; i <= k; ++i)cin >> total[i];vector<int> maxheap, minheap;for(int i = 1; i <= k; ++i){maxheapsize++;minheapsize = total[i] - maxheapsize;insertnum = total[i] - total[i-1];if(insertnum == 0 && !minheap.empty()){maxheap.push_back(minheap[0]);push_heap(maxheap.begin(), maxheap.end());//默認采用 < , 大堆pop_heap(minheap.begin(), minheap.end(), greater<int>());minheap.pop_back();}while(insertnum--){if (maxheap.empty()){maxheap.push_back(arr[arrindex]);}else{//----選擇插入哪個堆-----if (arr[arrindex] <= maxheap[0]){if(maxheap.size() >= maxheapsize){minheap.push_back(maxheap[0]);//大堆頂進入小堆push_heap(minheap.begin(), minheap.end(), greater<int>());pop_heap(maxheap.begin(), maxheap.end());//堆頂到末尾了maxheap.pop_back();//刪除到末尾的"堆頂"}maxheap.push_back(arr[arrindex]);push_heap(maxheap.begin(), maxheap.end());//默認采用 < , 大堆}else if (arr[arrindex] > maxheap[0]){if(minheap.size() >= minheapsize){maxheap.push_back(minheap[0]);push_heap(maxheap.begin(), maxheap.end());//默認采用 < , 大堆pop_heap(minheap.begin(), minheap.end(), greater<int>());minheap.pop_back();}minheap.push_back(arr[arrindex]);push_heap(minheap.begin(), minheap.end(), greater<int>());//小堆，采用 >}}arrindex++;}cout << maxheap[0] << endl;}return 0; }

總結

以上是生活随笔為你收集整理的POJ 1442 Black Box（大小堆，求第K小的元素）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。