首页 > 代码库 > hdu 4122 Alice's mooncake shop(单调队列)
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 <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
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<pii> Q;
queue<pii> 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\n", solve());
}
return 0;
}
hdu 4122 Alice's mooncake shop(单调队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。