CE16.【C++ Cont】练习题组16(堆专题)

#include <iostream>
#include <queue>  
using namespace std;
int main()
{
	priority_queue<int,vector<int>,greater<int>> q;
	int n,x,op;
	cin>>n;
	while(n--)
	{
		cin>>op;
		if (op==1)
		{
			cin>>x;
			q.push(x);
		}
		else if (op==2)
			cout<<q.top()<<endl;
		else	
			q.pop();
	}
    return 0;
}

提交结果

2.第 k 小的数

题目

https://ac.nowcoder.com/acm/problem/214362

分析

方法1:建小堆(不推荐)

录入所有数后,建小堆,由于堆顶是最小的元素,如果只从堆顶取出第k小的元素,那么需要删除堆顶元素(k-1)次,之后堆顶就是第k小,之前删除的元素保留在临时数组中,待打印第k小的元素后将删除过的元素再入堆

但这种方法有缺陷:时间复杂度太高(之前删除的元素再入堆占大量时间),不推荐使用

#include <iostream>
#include <queue>
#define endl "\n"  
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	priority_queue<int, vector<int>, greater<int>> q;//建小根堆
	vector<int> tmp;
	int n, m, k, x, op;
	cin >> n >> m >> k;
	while (n--)
	{
		cin >> x;
		q.push(x);
	}
	while (m--)
	{
		cin >> op;
		if (op == 1)
		{
			cin >> x;
			q.push(x);
		}
		else//op==2
		{
			if (q.size() < k)
				cout << "-1" << endl;
			else
			{
				int times = k;
				times--;
				while (times--)
				{
					tmp.push_back(q.top());
					q.pop();
				}
				cout << q.top() << endl;
				while (!tmp.empty())
				{
					q.push(tmp.back());
					tmp.pop_back();
				}
			}
		}
	}
	return 0;
}

就算写出来了,牛客网上也过不了,超时

方法2:建大堆(推荐)

之前在105.【C语言】数据结构之TopK问题详细分析文章中讲过建大堆的算法

和方法1恰好相反,删除大根堆的堆顶元素(n-k)次,剩下在堆中的元素是第1小的到第k小的,堆顶为第k小的

则维护大根堆只含k个元素即可,堆顶即为第k小的元素.

方法2代码

#include <iostream>
#include <queue>
#define endl "\n"  
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	priority_queue<int,vector<int>,less<int>> q;
	int n,m,k,x,op;
	cin>>n>>m>>k;
	while(n--)
	{
		cin>>x;
		q.push(x);
	}
	
	while(m--)
	{
		cin>>op;
		if (op==1)
		{
			cin>>x;
			q.push(x);		
		}
		while(q.size()>k)
			q.pop();
		if (op==2)
        {
            if (q.size()<k)
                cout<<"-1"<<endl;
            else
                cout<<q.top()<<endl;
        }
	}
    return 0;
}

注意while(m--)中的if判断和while(q.size()>k)的出场顺序,会影响结果的正确性

提交结果

3. 除2！

题目

https://ac.nowcoder.com/acm/problem/213140

分析

贪心算法:每次挑选出数组中最大的偶数来/2,这样可让数组中所有数之和尽可能小

最大的偶数怎么取? 答:使用大根堆! 设用sum来存储总和,如果堆顶为奇,正常将堆顶元素加到sum中,之后删除堆顶元素;如果堆顶为偶,看看k是否为正,k如果为正,先用tmp保存堆顶元素,再删除堆顶元素,将除以2后tmp的再入堆,k如果为负,正常将堆顶元素加到sum中,之后删除堆顶元素

代码

注意:本题使用int存储过不了,最大: $sum=10^9*(10^5-1)=10^{14}-10^9$ ,发现超出了int的存储范围!!

#include <iostream>
#include <queue>
#define endl "\n"  
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	priority_queue<unsigned long long,vector<unsigned long long>,less<unsigned long long>> q;
	vector<unsigned long long> tmp;
	unsigned long long n,k,x;
	unsigned long long sum=0;
	cin>>n>>k;
	while(n--)
	{
		cin>>x;
		q.push(x);
	}
	
	while(!q.empty())
	{
		if (q.top()%2)//堆顶为奇数
		{
			sum+=q.top();
			q.pop();	
		} 
		else//堆顶为偶数
		{
			if (k>0)
			{
				int tmp=q.top();
				q.pop();
				tmp/=2;
				q.push(tmp);
				k--;
			}
			else
			{
				sum+=q.top();
				q.pop();				
			} 
		} 
	}
	cout<<sum;
    return 0;
}