zoj 1200 Mining

这道题被划到了动态规划里面去了，结果就是一道模拟题，懒了一点，直接用stl的优先队列，重载了一下运算符，写的时候保证只能一个在采，因为如果需要的采的次数比可以生产的次数少，那么生产的次数等于需要采的次数，算个小剪枝。

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<map>

#include<iostream>

#include<vector>

#include<cstring>

#include<queue>

#include<string>

using namespace std;

int s,w,c,k,m;

struct node

{

    int t;

    node(int a):t(a) {}

};

bool operator <(const node &t1,const node &t2)

{

    return t1.t>t2.t;

}

priority_queue<node> q;

int solve()

{

    while(!q.empty())

            q.pop();

        int ans=(10000-0.5)/c+1;

        k=min(k,ans);

        int f=0;

        for(int i=1;i<=k;i++)

        q.push(node(m*i+s));

        int aa=-1;

        while(!q.empty())

        {

            node x=q.top();

            q.pop();

            if(x.t<aa)

                x.t=aa;

            aa=x.t+w;

            f++;

            if(f==ans)

                return x.t+w+s;

            q.push(node(x.t+w+s+s));

        }

}

int main()

{

    // freopen("input.txt","r",stdin);

    while(scanf("%d%d%d%d%d",&s,&w,&c,&k,&m)==5)

    {

        int  res=solve();

        printf("%d\n",res);

    }

}

再谈一下c++运算符重载，一篇博客的例子，优先队列的写法有很多，我还是习惯于结构体加单独重载函数，看起来比较清晰，好写。