http://hihocoder.com/contest/hiho153/problem/1
时间限制: 20000ms
单点时限: 2000ms
内存限制: 256MB
描述
小Hi最近在分析一支股票的价格走势,他需要一个程序来辅助分析。这个程序会接收3种消息(指令):
价格信息,格式是P timestamp price
:表示这支股票在 timestamp 时刻价格是 price。
删除价格指令,格式是R timestamp
:随着时间推移,小Hi会积累越来越多的价格数据。一些老旧的数据会变得不重要。这个指定会删除 timestamp 以前(包括 timestamp 时刻)的价格数据。
价格查询指令,格式是Q
:小Hi希望程序返回这只股票最高、最低和最近的价格。注意已经被删除的价格不应该被统计。
给定一个包含以上3种信息(指令)的序列,你能否帮助小Hi完成这个程序呢?
输入
第1行包含一个整数 N (1 ≤ N ≤ 500000),表示消息(指令)序列的长度。
第2 - N+1行,每行包含一条消息或指令。
输入保证价格信息是按照 timestamp 升序排列的,并且出现的 timestamp 和价格小于100000000。
输出
对于输入中每一条价格查询指令,输出当时最高、最低和最近的价格。
样例输入
10
P 1 77
P 2 73
P 5 70
P 7 74
Q
R 4
Q
P 8 78
R 5
Q
样例输出
77 70 74
74 70 74
78 74 78
分析
要求设计一个数据结构,处理一种二元数据(timestamp, price)
,可以进行以下操作:
- 插入
- 删除
timestamp
小于等于某个值的所有数据项 - 查询最大、最小的
price
和timestamp
最大的数据
仅前两个功能的话,可以用FIFO队列实现,难点在于如何快速同时获得最大和最小的元素以及最后插入的元素。
解决方案是用map
和multiset
协同实现。开一个map<int, int>
和multiset<int>
,前者用来存(timestamp, price)
,后者存所有price
(包括重复出现的)。
- 插入元素时,两个容器同时插入
- 删除元素时,从
map
的map.begin()
开始,检查对应元素的timestamp
是否小于给定值,是则erase
,同时在multiset
中erase
相应的price值,这样不断检查map
的首元素,直到map.begin()
的timestamp
大于给定值为止 - 查询时,最大值对应
multiset.rbegin()
,最小值对应multiset.begin()
,最后插入的price对应map.rbegin()
C++
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
int N;
map<int, int> m; // (timestamp, price)
multiset<int> prices;
map<int, int>::iterator it;
multiset<int>::iterator it_prices;
int high, low, last;
void Insert(int timestamp, int price)
{
m[timestamp] = price;
prices.insert(price);
}
void Delete(int timestamp)
{
if (m.empty()) return;
int price;
it = m.begin();
while (it != m.end() && it->first <= timestamp)
{
price = it->second;
m.erase(it);
it_prices = prices.find(price);
prices.erase(it_prices);
it = m.begin();
}
}
void Get()
{
high = *(prices.rbegin());
low = *(prices.begin());
last = m.rbegin()->second;
cout << high << " " << low << " " << last << endl;
}
int main()
{
char cmd;
int timestamp, price;
m.clear();
prices.clear();
scanf("%d", &N); getchar();
for (int i = 0; i < N; ++i)
{
scanf("%c", &cmd); getchar();
if (cmd == 'P')
{
scanf("%d%d", ×tamp, &price); getchar();
Insert(timestamp, price);
}
else if (cmd == 'R')
{
scanf("%d", ×tamp); getchar();
Delete(timestamp);
}
else
{
Get();
}
}
return 0;
}