单调队列-Hdu-4122-Alice's mooncake shop

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4122

题目意思：

一家月饼店，有n个订单，从2001年1月1日0时开始24小时营业开m个小时，且每个时间点做一个月斌的花费不一样，每个订单由时间（年月日时）定月饼数量组成。店主在每个整时点都可以做月饼，并且做月饼的时间可以忽略。每个月饼有保质期t,保存每个月饼每小时需花费s。求完成所有订单，最少的花费。

解题思路：

1、先算出每个订单的小时点。

2、对每个订单时间点i,很显然花费min(cost[j]+(i-j)*s)(i-j<=t)最划算。cost[j]+(i-j)*s=cost[j]-j*s+i*s,所以对于每个i,求出前面的满足j>=i-t,的cost[j]-j*s的最小值即可，很显然用单调队列可以维护。

代码：

 

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

//0表示平年，1表示闰年
int days[2][13]={0,31,28,31,30,31,30,31,31,30,31,30,31,
0,31,29,31,30,31,30,31,31,30,31,30,31};
int dd[2]={365,366}; //每年的天数
map<string,int>myp;
string  mon;
#define Maxn 2700
#define Maxm 110000
ll pp[Maxn],hh[Maxn];//订单的月饼数量和时间点
ll q[Maxm],cost[Maxm];//花费
ll Mi[Maxm];//Mi[i]表示时间点i时的最小花费单价
ll n,m;

bool isleap(int y) //是否为闰年
{
    if((y%4==0&&y%100)||(y%400==0))
        return true;
    return false;
}

ll Cal(int y,int m,int d,int h) //计算距离2000年1月1日0时的小时数，从开始标记
{
    ll res=0;
    for(int i=2000;i<y;i++) //计算前面的年份
        res+=dd[isleap(i)]*24;
    int is=isleap(y);
    for(int i=1;i<m;i++) //计算当前年的前面月的天数
        res+=days[is][i]*24;
    res+=(d-1)*24;//当月的小时数
    res+=(h+1); //从1小时开始记
    return res;

}

int main()
{
   myp["Jan"]=1,myp["Feb"]=2,myp["Mar"]=3,myp["Apr"]=4;
   myp["May"]=5,myp["Jun"]=6,myp["Jul"]=7,myp["Aug"]=8;
   myp["Sep"]=9,myp["Oct"]=10,myp["Nov"]=11,myp["Dec"]=12;
   int mon,day,yea,hour;

   while(scanf("%I64d%I64d",&n,&m)&&n+m)
   {
       for(int i=1;i<=n;i++)
       {
           string a;
           cin>>a>>day>>yea>>hour>>pp[i];
           hh[i]=Cal(yea,myp[a],day,hour);
       }
      ll t,s;

       scanf("%I64d%I64d",&t,&s);
       for(int i=1;i<=m;i++)
       {
           scanf("%I64d",&cost[i]);
           cost[i]-=i*s; //需要维护的值
       }

       int head=1,tail=0; //从1开始标号

      // printf("%I64d\n",m);
       for(int i=1;i<=m+1;i++)
       {
           while(head<=tail&&cost[q[tail]]>=cost[i])
                tail--;
           q[++tail]=i;
           while(head<=tail&&q[head]+t<i)
                head++;
           Mi[i]=cost[q[head]]+i*s;
       }
       //printf(":%I64d\n",Mi[10]);
       ll ans=0;
       for(int i=1;i<=n;i++)
            ans+=Mi[hh[i]]*pp[i];
       printf("%I64d\n",ans);
            //printf("%I64d\n",Mi[hh[i]]*pp[i]);

   }
   return 0;
}