单调队列-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 110000ll 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;}