HDU 4122 Alice's mooncake shop （单调队列/线段树）

时间：2021-03-11 11:19:51

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4122

题意：好难读懂，读懂了也好难描述，亲们就自己凑合看看题意把

题解：开始计算每个日期到2000/1/1日0点有多少个小时，然后求出每个小时的时候每个的最小单价（包括成本+储存费用）

使用单调队列，维护队列，使之到i 生产的最优

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;

#define si1(a) scanf("%d",&a)

#define si2(a,b) scanf("%d%d",&a,&b)

#define sd1(a) scanf("%lf",&a)

#define sd2(a,b) scanf("%lf%lf",&a,&b)

#define ss1(s)  scanf("%s",s)

#define pi1(a)    printf("%d\n",a)

#define pi2(a,b)  printf("%d %d\n",a,b)

#define mset(a,b)   memset(a,b,sizeof(a))

#define forb(i,a,b)   for(int i=a;i<b;i++)

#define ford(i,a,b)   for(int i=a;i<=b;i++)

typedef __int64 LL;

const int N=110001;

const int M=1000007;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-7;

LL n,m,s,t;

char ss[100];

int mm[13],yy[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

map<string,int> mp;

struct node

{

    int t,num;

}q[3333*4],order[3333];

bool isrun(int y)

{

    if(y%400==0||(y%4==0&&y%100!=0))

        return true;

    return false;

}

int run(int y1,int y2)

{

    int num=0;

    for(int i=y1;i<y2;i++)

        if(i%400==0||(i%4==0&&i%100!=0))

            num++;

    return num;

}

int main()

{

    mm[0]=0;

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

        mm[i]=mm[i-1]+yy[i];

    mp["Jan"]=1;

    mp["Feb"]=2;

    mp["Mar"]=3;

    mp["Apr"]=4;

    mp["May"]=5;

    mp["Jun"]=6;

    mp["Jul"]=7;

    mp["Aug"]=8;

    mp["Sep"]=9;

    mp["Oct"]=10;

    mp["Nov"]=11;

    mp["Dec"]=12;

    while(scanf("%I64d%I64d",&n,&m)&&(n+m))

    {

        for(int i=0;i<n;i++)

        {

            string ss;

            int ri,nian,shi,ge;

            cin>>ss;

            scanf("%d%d%d%d",&ri,&nian,&shi,&order[i].num);

            int yue=mp[ss];

            int sum=(nian-2000)*365+run(2000,nian);

            sum+=mm[yue-1]+ri-1;

            if(yue>2&&isrun(nian))   sum++;

            order[i].t=sum*24+shi;

        }

        int top=0,tail=0,p=0,t,s;

        LL sum=0;

        scanf("%d%d",&t,&s);

        for(int i=0;i<m;++i)

        {

            int a;

            scanf("%d",&a);

            while(top<tail && q[tail-1].num+(i-q[tail-1].t)*s>=a)--tail;

            q[tail].num=a,q[tail++].t=i;

            while(p<n && i == order[p].t)

            {

                while(q[top].t+t<i)++top;

                sum+=(q[top].num+(i-q[top].t)*s)*order[p++].num;

            }

        }

        printf("%I64d\n",sum);

    }

    return 0;

}

/*

1 10

Jan 1 2000 9 10

5 2

20

20

20

10

10

8

7

9

5

10

0 0

*/

相关文章