HDU 4122 Alice's mooncake shop(贪心、RMQ)

题意:

$给定N\le 2500个订单,升序排列,保证合法$
$现在有个店开M\le 10^5小时,每小时做月饼的价格都不一样,不考虑做月饼的时间$
$每个月饼的保质期是t\le 10^5小时,每小时的花费为s\le 200$
$订单可以现做现卖,问如何制作才能满足所有订单,并使得总花费最小$
$求这个花费$

分析:

$首先先解析日期都成小时$
$对于i小时的订单,显然应该取[i-t+1, i]的最小的那个花费$
$为了方便处理,假设都在最后一天买,显然某一天的花费应该a_i+(m-i)\times s$
$之后取min\{cost[i-t+1, i]\},再减去多算的(m-i)\times s$
$然后就做完了$
$时间复杂度O(nlogm+m)$
$妈蛋,我样处理日期要考虑重复的情况,赛上T到死了。。。while与if的一字之差$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
//
// Created by TaoSama on 2016-05-02
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
#include <tuple>
#include <cassert>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 2e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m;
int t, s;
struct Order {
int y, m, d, h;
int id;
void read() {
scanf("%d%d%d%d", &d, &y, &h, &r);
}
void see() {
printf("(%d, %d, %d, %d)\n", y, m, d, h);
}
int r;
} o[2505];
void RE() {
printf("%d\n", *((int*)0));
}
typedef long long LL;
LL a[N];
struct SparseTable {
int n;
LL dp[20][N];
void init(int _n, LL* a) {
n = _n;
for(int i = 1; i <= n; ++i) dp[0][i] = a[i];
for(int i = 1; (1 << i) <= n; ++i)
for(int j = 1; j + (1 << i) - 1 <= n; ++j)
dp[i][j] = min(dp[i - 1][j],
dp[i - 1][j + (1 << i - 1)]);
}
LL RMQ(int l, int r) {
int k = 31 - __builtin_clz(r - l + 1);
return min(dp[k][l], dp[k][r - (1 << k) + 1]);
}
} st;
char mm[][10] = {"", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
int mdays[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool isLeap(int y) {
return y % 4 == 0 && y % 100 || y % 400 == 0;
}
void go(int& y, int& m, int& d, int& h) {
++h;
if(h >= 24) h = 0, ++d;
int cur = mdays[m];
if(m == 2 && isLeap(y)) ++cur;
if(d > cur) d -= cur, ++m;
if(m > 12) m -= 12, ++y;
}
int getTime(int m, int day, int year, int h) {
int res = 0;
for(int i = 2000; i < year; i++) {
if(isLeap(i))res += 366 * 24;
else res += 365 * 24;
}
for(int i = 1; i < m; i++) {
res += mdays[i] * 24;
if(isLeap(year) && i == 2)res += 24;
}
for(int i = 1; i < day; i++)res += 24;
res += h + 1;
return res;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d%d", &n, &m) == 2 && (n || m)) {
for(int i = 1; i <= n; ++i) {
char mon[10]; scanf("%s", mon);
o[i].read();
for(int j = 1; j <= 12; ++j) {
if(!strcmp(mm[j], mon)) {
o[i].m = j;
break;
}
}
}
scanf("%d%d", &t, &s);
int Y = 2000, M = 1, D = 1, H = 0;
for(int j = 1, i = 1; ; ++j) {
// o[i].see();
while(make_tuple(Y, M, D, H) ==
make_tuple(o[i].y, o[i].m, o[i].d, o[i].h)) {
o[i].id = j;
// printf("%d = %d\n", i, j);
++i;
}
if(i == n + 1) break;
go(Y, M, D, H);
}
for(int i = 1; i <= m; ++i) {
scanf("%I64d", a + i);
a[i] += 1LL * (m - i) * s;
}
st.init(m, a);
LL ans = 0;
for(int i = 1; i <= n; ++i) {
int d = o[i].id;
LL cur = st.RMQ(max(1, d - t + 1), d);
cur -= 1LL * (m - d) * s;
ans += cur * o[i].r;
}
printf("%I64d\n", ans);
}
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到