2020icpc亚洲区域赛（济南）M题Cook Pancakes（小根堆的应用）

一.题意：

你有一个锅，锅的容量是k个饼，就是可以同时煎k个饼的一面，你有n个饼需要煎双面，饼面煎熟需要1小时，问你使用容量为k的锅去煎n个饼至少需要几小时。

二.用小根堆的目的（思路）：

小根堆里面存0/1/2 0代表1面没煎过，1代表煎过一面，2代表这个饼已经煎完了。

优先煎煎过次数较少的饼

使得每次剩下两面都没煎的饼尽量少（这样的话剩余的同类面（在一个饼上，不能同时煎的面）就会尽量少）这样的话就能够充分利用锅，可以尽可能的一次煎多个饼的面。

三.代码：

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=100;
priority_queue<int,vector<int>,greater<int>> heap;//小根堆形式
int main()
{
    int n,k;
    cin>>n>>k;
    if(n<=k)//如果这样的话，如果进入下面的小根堆循环，就会是1
//因为如果容量大于个数的话，两个同类面会同时煎
    {
        cout<<2<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        heap.push(0);
    }
    int h=0;
    while(heap.top()<2)
    {
        int t=k;
        while(t--)
        {
            heap.push(heap.top()+1);
            heap.pop();
        }
        h++;
    }
    cout<<h<<endl;
}

我那年的集训队面试题，真是怀念qwq。