hdu 4122 Alice 's mooncake shop (단조 로 운 대기 열)

제목 링크: hdu 4122 Alice 's mooncake shop
제목: N 과 M 을 정 하면 N 개의 주문 이 있 고 M 시간 에 월병 을 만 들 수 있 으 며 시간 에 따라 계산 할 수 있 으 며 임의의 시간 에 몇 개의 월병 을 만 들 수 있다.이어서
N 행위 N 개의 주문 정보, 시간 과 수량 을 포함 합 니 다.T 와 S 를 지정 하면 월병 의 품질 보증 시간 과 보관 시간 당 비용 을 표시 합 니 다.그리고 M 행동.
매 순간 월병 을 만 드 는 대가 에 대응 하 다.최소한 얼마의 대 가 를 치 르 고 모든 주문 서 를 완성 하 느 냐 고 물 었 다.
문제 풀이 방향: 단조 로 운 대기 열 이나 RMQ, 단조 로 운 대기 열 은 하나의 deque 로 대가 가 증가 하 는 대기 열 을 유지 하고 매번 머리 유통 기한 이 부족 한 것 을 제거 합 니 다.
RMQ 는 전처리 처 의 각 구간 시간 대 가 를 최소 화 할 수 있 으 며, 저장 대 가 를 더 해 야 하 며, 각 주문 에 대해 서 는 조회 표 앞 위치 에서 T 앞으로 만 가면 된다.
시간 이내 의 최소 값 이면 된다.

#include 
#include 
#include 
#include 

using namespace std;
const char month[15][10] = {"", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov"};
const int day[15] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
typedef pair<int,int> pii;
typedef long long ll;

int N, M;
deque Q;
queue G;

inline int get_month(char* s) {
    for (int i = 1; i <= 11; i++)
        if (strcmp(s, month[i]) == 0)
            return i;
    return 12;
}

inline bool Leap_year(int x) {
    return (x % 4 == 0 && x % 100) || x % 400 == 0;
}

int get_time() {
    char mon[10];
    int y, d, h, m;
    scanf("%s%d%d%d", mon, &d, &y, &h);
    m = get_month(mon);

    int ret = 0;
    for (int i = 2000; i < y; i++)
        ret += Leap_year(i) ? 366 : 365;

    for (int i = 1; i < m; i++) {
        if (i == 2 && Leap_year(y))
            ret += 29;
        else
            ret += day[i];
    }
    ret += d - 1;
    return ret * 24 + h;
}

void init () {
    int ti, x;
    Q.clear();

    for (int i = 0; i < N; i++) {
        ti = get_time();
        scanf("%d", &x);
        G.push(make_pair(x, ti));
    }
}

ll solve () {
    int S, T, x;
    ll ret = 0;
    scanf("%d%d", &T, &S);
    for (int i = 0; i < M; i++) {
        scanf("%d", &x);
        while (!Q.empty() && x <= Q.back().first + (i - Q.back().second) * S)
            Q.pop_back();
        Q.push_back(make_pair(x, i));
        while (!G.empty() && i == G.front().second) {
            while (!Q.empty() && Q.front().second + T < i)
                Q.pop_front();
            ret += (Q.front().first + (i - Q.front().second) * S) * G.front().first;
            G.pop();
        }
    }
    return ret;
}

int main () {
    while (scanf("%d%d", &N, &M) == 2 && N + M) {
        init();
        printf("%I64d
", solve());
    }
    return 0;
}