MENU

HDU 4122 Alice's mooncake shop

2019-07-25 • 阅读: 21 • 阅读设置

单调队列

正式由于每个月饼可以保存T小时,转化为滑动窗口,不超过T(这里我认为是T+1,即第i小时生产的月饼,i+T小时仍然可以用,所以T+1个小时)的窗口的最小值。
队列的初始化很重要,wa了好久。

#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int M[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int a[N],time[N],b[N];
int S, T;
int n, m;
int q[N];
int MON(char *m){
    if (strcmp(m, "Jan") == 0)return 1;
    if (strcmp(m, "Feb") == 0)return 2;
    if (strcmp(m, "Mar") == 0)return 3;
    if (strcmp(m, "Apr") == 0)return 4;
    if (strcmp(m, "May") == 0)return 5;
    if (strcmp(m, "Jun") == 0)return 6;
    if (strcmp(m, "Jul") == 0)return 7;
    if (strcmp(m, "Aug") == 0)return 8;
    if (strcmp(m, "Sep") == 0)return 9;
    if (strcmp(m, "Oct") == 0)return 10;
    if (strcmp(m, "Nov") == 0)return 11;
    return 12;
}
bool LeapYear(int &year){
    return year % 4 == 0 && year % 100 || year % 400 == 0;
}
int Time(int year, int Mon, int d, int h){
    int t = 0;
    for (int i = 2000; i<year; ++i){
        if (LeapYear(i))t += 366;
        else t += 365;
    }
    bool flag = LeapYear(year);
    for (int i = 1; i<Mon; ++i){
        if (flag && i == 2)t += 29;
        else t += M[i];
    }
    t += d - 1;
    return t * 24 + h;
}
int main()
{
    while (scanf("%d%d", &n, &m)!=EOF)
    {
        if (!n&&!m) break;
        for (int i = 0; i < n; i++)
        {
            int year, day, t;
            char mon[10];
            scanf("%s%d%d%d%d", &mon, &day, &year, &t, &a[i]);
            time[i] = Time(year, MON(mon), day, t);
        }
        scanf("%d%d", &T, &S);
        int l = 1, r = 0,idx=0;
        ll ans = 0;
        for (int i = 0; i < m; i++)
        {
            scanf("%d", &b[i]);
            while (l <= r && (b[i] <= b[q[r]] + (i - q[r])*S)) r--;
            q[++r] = i;
            while (l <= r&&i - q[l]>T) l++;
            while (idx < n&&i == time[idx]){
                ans += a[idx]*(b[q[l]] + (i - q[l])*S);
                idx++;
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码