拼多多笔试编程第三题

[编程|25分] 简单易懂的秒杀服务

实现一个简易的秒杀服务，有3个接口：

1. 添加一个秒杀活动 addActivity(int startTime, int endTime, int goodsId, int limitQuantity)

参数说明：

    * 时间区间为左闭右开：[startTime, endTime) 。数据保证 startTime < endTime，startTime 大于当前时间戳
    * goodsId 一定为存在的商品id。每个goodsId至多添加一次秒杀活动。
    * limitQuantity > 0 

返回值有以下两种情况：

    * 添加成功，返回秒杀活动ID (从0开始自增)
    * 秒杀商品数量大于商品库存，添加失败，返回-1

2. 购买秒杀商品 buyGoods(int activityId, int quantity)

参数说明：

    * activityId 一定是请求时存在的活动id
    * quantity > 0 

返回值有以下三种情况：

    * 购买成功，减少库存，返回0
    * 购买数量大于秒杀商品剩余数量，购买失败，返回-1
    * 秒杀未开始或已结束，购买失败，返回-1

3. 获取秒杀活动列表 getActivityList() 获取当前时刻的秒杀活动列表

秒杀列表排序方式：进行中(未售罄) > 进行中(售罄) > 未开始 

    * 对于「进行中(未售罄)」：依次按商品人气值从高到低、商品ID从小到大排序 
    * 对于「进行中(已售罄)」：依次按最后卖出时间从晚到早、商品人气值从高到低、商品ID从小到大排序 
    * 对于「未开始」：依次按开始时间从早到晚、商品人气值从高到低、商品ID从小到大排序
    * 对于已结束的秒杀，不返回。 

返回秒杀活动id列表

商品拥有以下属性：

* 商品ID，32位非负整数 
* 人气值，32位非负整数 
* 库存，32位非负整数

现给出一串请求，每个请求的格式为：时间戳 函数名 参数。请对每个请求都输出其返回结果 (请求已经按照时间先后顺序排序过) 。

数据范围：

* 商品数量 N <= 10,000
* 请求数量 M <= 10,000
* add 数量 A <= 1,000
* buy 数量 B <= 10,000 
* list 数量 L <= 100

输入描述:

第一行是两个整数 N 和 M ，分别表示商品数量和请求数量。
接下来有 N 行，每行表示一个商品，具体格式为：3个整数(被空格分隔)分别表示商品ID，人气值，库存
接下来有 M 行，每行表示一个请求，请求已经按时间戳从小到大排序。
具体格式为：时间戳 请求类型 请求参数...
  * 时间戳：正整数
  * 请求类型，共三种："add", "buy" 和 "list"
  * 请求参数：按题目描述中的顺序，参数之间空格分隔

输出描述:

对每个请求，输出其返回值，一个请求的输出占一行：
  * add：成功输出id，失败输出-1
  * buy：成功输出0，失败输出-1
  * list：输出活动id列表，按要求的顺序，相邻数字之间用一个空格分隔。若列表为空，则输出空行。

示例1

输入

6 13
1001 1 10
1002 1 10
1003 2 10
1004 2 10
1005 2 10
1006 3 10
1 add 2 20 1001 10
2 buy 0 1
3 buy 0 10
4 add 5 6 1002 2
5 list
6 buy 1 1
7 add 10 20 1003 11
8 add 10 20 1003 8
9 add 10 20 1004 3
10 add 11 20 1005 5
11 add 20 30 1006 1
12 buy 3 3
13 list

输出

0
0
-1
1
0 1
-1
-1
2
3
4
5
0
2 4 0 3 5

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

struct goods{
	goods() :goodsId(0), sellDoneTime(INT_MAX), activityId(-1), Populity(0), LimitQuility(0), Left(0), startTime(0), endTime(0), LIMIT_TAG(0){};
	int goodsId;
	int Populity;
	int Left;
	int LimitQuility;
	int startTime, endTime;
	int LIMIT_TAG;
	int activityId;
	int sellDoneTime;
	//0未开始 1已开始  2卖光 -1已结束
};

bool cmp1(const goods &lsh, const goods &rsh){
	return lsh.Populity > rsh.Populity || (lsh.Populity == rsh.Populity && lsh.goodsId < rsh.goodsId);
}
bool cmp0(const goods &lsh, const goods &rsh){
	return lsh.startTime < rsh.startTime || (lsh.startTime== rsh.startTime && lsh.Populity > rsh.Populity) ||
		(lsh.startTime == rsh.startTime && lsh.Populity == rsh.Populity && lsh.goodsId < rsh.goodsId);}
bool cmp2(const goods &lsh, const goods &rsh){
	return lsh.sellDoneTime > rsh.sellDoneTime || (lsh.startTime == rsh.startTime && lsh.Populity > rsh.Populity) ||
		(lsh.startTime == rsh.startTime && lsh.Populity == rsh.Populity && lsh.goodsId < rsh.goodsId);
}

struct MS{
	MS(int n){
		AllThing = vector<goods>(n);
		t_id = -1;
	};
	int addActivity(int startTime, int endTime, int goodsld, int limitQuantity);
	int buyGoods(int activityId, int quantity, int time);
	void getActivityList(int time);
	vector<goods> AllThing;
	vector<goods> LimitVEC;
	int t_id;
};

int MS::addActivity(int startTime, int endTime, int goodsld, int limitQuantity){
	int i;
	for (i = 0; i < AllThing.size(); i++){
		if (AllThing[i].goodsId == goodsld)
		{
			break;
		}
	}
	if (i >= AllThing.size() || AllThing[i].Left < limitQuantity || AllThing[i].LIMIT_TAG)
	{
		//无法秒杀
		cout << "-1" << endl;
		return -1;
	}
	AllThing[i].Left -= limitQuantity;
	AllThing[i].LIMIT_TAG = 1; 
	AllThing[i].startTime = startTime;
	AllThing[i].endTime = endTime;
	AllThing[i].LimitQuility = limitQuantity;
	AllThing[i].activityId = ++t_id;;
	LimitVEC.push_back(AllThing[i]);
	cout << t_id << endl;
	return  t_id;
}

int MS::buyGoods(int activityId, int quantity, int time){
	if (activityId >= LimitVEC.size() ||quantity > LimitVEC[activityId].LimitQuility|| time < LimitVEC[activityId].startTime || time >= LimitVEC[activityId].endTime)
	{
		cout << "-1" << endl;
		return -1;
	}
	LimitVEC[activityId].LimitQuility -= quantity;
	if (LimitVEC[activityId].LimitQuility == 0)
	{
		LimitVEC[activityId].LIMIT_TAG = 2;
		LimitVEC[activityId].sellDoneTime = time;
	}
	cout << "0" << endl;
	return 0;
}

void MS::getActivityList(int time){
	vector<goods> VEC0;
	vector<goods> VEC1;
	vector<goods> VEC2;
	for (int i = 0; i < LimitVEC.size();i++)
	{
		//没开始
		if (LimitVEC[i].LIMIT_TAG == 1 && LimitVEC[i].startTime > time){
			VEC0.push_back(LimitVEC[i]);
		}
		//结束了
		else if (LimitVEC[i].LIMIT_TAG > 0&& LimitVEC[i].endTime <= time){
		}
		//没卖完
		else if (LimitVEC[i].LIMIT_TAG == 1 && LimitVEC[i].endTime > time)
		{
			VEC1.push_back(LimitVEC[i]);
		}
		else if (LimitVEC[i].LIMIT_TAG == 2){
			VEC2.push_back(LimitVEC[i]);
		}
	}
	if (!VEC1.empty())
	{
		sort(VEC1.begin(), VEC1.end(), cmp1);
	}
	if (!VEC2.empty())
	{
		sort(VEC2.begin(), VEC2.end(), cmp2);
	}
	if (!VEC0.empty())
	{
		sort(VEC0.begin(), VEC0.end(), cmp0);
	}
	VEC1.insert(VEC1.end(), VEC2.begin(), VEC2.end());
	VEC1.insert(VEC1.end(), VEC0.begin(), VEC0.end());
	if (!VEC1.empty()){
		for (int i = 0; i < (int)VEC1.size() - 1; i++)
			cout << VEC1[i].activityId << " ";
		cout << VEC1[VEC1.size() - 1].activityId << endl;
	}
	
}

int main(){
	int n,m;
	cin >> n >> m;
	MS ms(n);
	map<string, int> MP;
	MP["add"] = 0;
	MP["buy"] = 1;
	MP["list"] = 2;
	for (int i = 0; i < n;i++)
	{
		cin >> ms.AllThing[i].goodsId >> ms.AllThing[i].Populity >> ms.AllThing[i].Left;
	}
	for (int i = 0; i < m;i++)
	{
		int time,a,b,c,d;
		string ope;
		cin >> time >> ope;

		switch (MP[ope]){
		//add
		case 0:
			cin >> a >> b >> c>>d;
			ms.addActivity(a, b, c, d);
			break;
		//buy
		case 1:
			cin >> a >> b;
			ms.buyGoods(a, b, time);
			break;
		//list
		case 2:
			ms.getActivityList(time);
			break;
		}
	}
	return 0;
}