TopCoder----卖柠檬 - L.J.SHOU的专栏 - 博客频道 - CSDN.NET
1. 题目描述
2. 分析
采用如下的策略,每天尽可能多地生产,并且优先卖生产日期久的。。采用一个队列。。
1. 题目描述
Problem Statement | |||||||||||||
You are playing a game called Slime Tycoon.You will be selling Slimonades in this game, and your goal is to sell as many as you can. The game will consist of N game days, numbered 0 through N-1 in order.You are given two vector <int>s morning and customers with N elements each, and an int stale_limit.These represent constraints on how many Slimonades you can produce and sell, as explained below. In each game day, three things happen, in the following order:
| |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Limits | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
- | morning will contain between 2 and 50 elements, inclusive. | ||||||||||||
- | Each element of morning will be between 0 and 10000, inclusive. | ||||||||||||
- | customers will contain the same number of elements as morning. | ||||||||||||
- | Each element of customers will be between 0 and 10000, inclusive. | ||||||||||||
- | stale_limit will be between 1 and N, inclusive. | ||||||||||||
Examples | |||||||||||||
|
采用如下的策略,每天尽可能多地生产,并且优先卖生产日期久的。。采用一个队列。。
class SlimeXSlimonadeTycoon { public: int sell(vector <int> morning, vector <int> customers, int stale_limit) { if(morning.empty()) return 0; int que[100000]; int front = 0, rear = 0; int count(0); for(int i=0; i<morning.size(); ++i) { if(front - rear == stale_limit) ++rear; que[front++] = morning[i]; while(rear < front && customers[i] > 0) { if(que[rear] > customers[i]){ count += customers[i]; que[rear] -= customers[i]; break; } else{ count += que[rear]; customers[i] -= que[rear]; ++rear; } } } return int(count) ; } };Read full article from TopCoder----卖柠檬 - L.J.SHOU的专栏 - 博客频道 - CSDN.NET