点击打开vjudge题目链接

Alice has opened up a 24-hour mooncake shop. She always gets a lot of orders. Only when the time is K o’clock sharp( K = 0,1,2 …. 23) she can make mooncakes, and We assume that making cakes takes no time. Due to the fluctuation of the price of the ingredients, the cost of a mooncake varies from hour to hour. She can make mooncakes when the order comes,or she can make mooncakes earlier than needed and store them in a fridge. The cost to store a mooncake for an hour is S and the storage life of a mooncake is T hours. She now asks you for help to work out a plan to minimize the cost to fulfill the orders.

题意:有一个蛋糕店,在某个时刻会有一些订单,你可以选择在订单之前的任意时刻做好。在每个时刻做一个蛋糕都有不同的花费,并且蛋糕有固定的保存开销和保质期,问什么时候做蛋糕使得开销最小。

分析:这道题是2011年福州亚洲区域赛的题目,第一题是曾经做过的象棋~~~~(>_<)~~~~ 。训练比赛打秃了,这题一看看不懂就没做,其实并不难,就是用时间上的单调队列模拟。做蛋糕的队列前面的要优于后面的,但可能会超过保质期,这样不断维护一个做蛋糕随时间的队列即可,当订单到来的时候选择之前的某个时刻做出来。

另外这道题实践证明list维护单调队列要比deque维护快,因为deque可能会重新分配大块内存,而list直接用指针指向单个内存。这样用list模拟这个单调队列即可。

C++代码如下

#include <bits/stdc++.h>
using namespace std;

struct Order{
    int time, num;
};
struct Moon{
    int time, spend;
};
map<string, int> dict = {
        {"Jan", 1}, {"Feb", 2}, {"Mar", 3}, {"Apr", 4},
        {"May", 5}, {"Jun", 6}, {"Jul", 7}, {"Aug", 8},
        {"Sep", 9}, {"Oct", 10}, {"Nov", 11}, {"Dec", 12}
};
const int monthDay[2][15] = {
        {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
        {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
list<Order> order;
list<Moon> moon;
int n, m, t, s;

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

int getTime() {
    int year, day, hour; string month;
    cin >> month >> day >> year >> hour;
    int res = 0;
    for(int i = 2000; i < year; ++i)
        res += leapYear(i) ? 366 * 24 : 365 * 24;
    for(int i = 1; i < dict[month]; ++i)
        res += monthDay[leapYear(year)][i] * 24;
    res += (day - 1) * 24;
    res += hour;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    while(cin >> n >> m, n || m) {
        order.clear(); moon.clear();
        for (int i = 0; i < n; ++i) {
            Order cur; cur.time = getTime();
            cin >> cur.num;
            order.push_back(cur);
        }
        cin >> t >> s;
        long long res = 0;
        for(int i = 0; i < m; ++i) {
            int cost; cin >> cost;
            while(!moon.empty() && moon.back().spend + s * (i - moon.back().time) >= cost)
                moon.pop_back();
            moon.push_back(Moon{i, cost});
            while(!order.empty() && i == order.front().time) {
                while(!moon.empty() && i - moon.front().time > t)
                    moon.pop_front();
                res += order.front().num * (moon.front().spend + s * (i - moon.front().time));
                order.pop_front();
            }
        }
        cout << res << endl;
    }
    return 0;
}

欢迎留言