Alice's mooncake shop HDU - 4122 | 单调队列

单调队列。。

题意：
Alice开了家月饼店，现有2500笔订单，订单包括某小时（2000年1月1日0点算第1个小时的开始）和需要的月饼数量。然后给你前100000小时的信息，包括第i个小时做1个饼的花费cost[i]。然后给你月饼的保质期T（说明订单i只能买[order[i].hour-T ,order[i].hour ]这个区间生产的饼）和保存1小时的花费S，让你求最小的花费满足所有订单。
分析：

• 注意可能有多个订单在同一个时间
• 每次维护完上升序列后，判断一下当前时间有无订单，有则维护区间长度。
  代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 1e5;
const int inf = 0x3f3f3f3f;
struct node1
{
    ll tim, num;
    node1(ll a = 0, ll b = 0) : tim(a), num(b){}
};
struct node2
{
    ll tim, cost;
    node2(ll a = 0, ll b = 0) : tim(a), cost(b){}
};
string mon[20]={"", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov","Dec"};
int day[20]={0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int n, m;

bool judge(int year)
{
    return year % 400 == 0 || year % 4 == 0 && year % 100;
}

ll gettime(int year, string month, int d, int hour)
{
    ll days = 0;
    for(int i = 2000; i < year; i++)
        days += judge(i) ? 366 : 365;
    int k = 0;
    for(; ; k++) if(mon[k] == month) break;
    for(int i = 1; i < k; i++)
        if(judge(year) && i == 2) days += 29;
        else days += day[i];
    days += d - 1;
    return days * 24 + hour;
}

int main()
{
    while(cin >> n >> m)
    {
        if(!n && !m) return 0;
        deque<node1> q1;
        deque<node2> q2;
        string month;
        ll day, year, hour;
        ll num;
        
        for(int i = 1; i <= n; i++)
        {
            cin >> month >> day >> year >> hour >> num;
            ll tim = gettime(year, month, day, hour);
            //print(tim);
            q1.push_back(node1(tim, num));
        }
        ll len, money; cin >> len >> money;
        ll res = 0;
        for(int i = 0; i < m; i++)
        {
            ll x; cin >> x; //每个月饼价格
            while(!q2.empty() && x <= q2.back().cost + (i - q2.back().tim) * money) 
                q2.pop_back();
            q2.push_back(node2(i, x));
            while(!q1.empty() && q1.front().tim == i)
            {
                while(!q2.empty() && q2.front().tim < i - len)
                    q2.pop_front();
                res += ((i - q2.front().tim) * money + q2.front().cost) * q1.front().num;
                q1.pop_front();
            }
        }
        cout << res << endl;
    }
}