蓝桥杯2019年第十届省赛真题-外卖店优先级

题目

题目链接

题解

思维吧？（离散化）

虽然N，M，T都是1e5，但是订单数量有限，这就导致想让每个店铺每个时间都有订单是不可能的，如果店铺种类多了起来，由于订单有限，那么每个店铺得到的订单就会很少，对于两个订单之间消耗的得分就可以避免遍历，直接通过减法得到。因此我们只需要遍历每个订单即可。先将订单按时间从小到大排序，保证按时间升序排列，再处理即可。

注意两个点：

1. 如果存在多个同一时刻同一店铺的订单，需要特殊处理，因为该店铺的上一次订单时间与这一次订单时间之差为0，需要减去的两次订单之间导致得分降低的值为0，即t2-t1，而如果两次订单时间不一样，则得分会降低这一次订单时间-上一次订单时间+1，即t2-t1+1。这两种情况的降低值不同，需要分开处理。
2. 判断是否还在系统中的语句所在位置。判断是否出系统的判断要在减去订单之间导致得分降低的值，而判断是否入系统则是在加上本次订单的得分后进行的，因为只要一旦得分不超过3了，就会出系统。如果将两个判断均放在加上本次订单的得分后进行，则可能存在进行完减法后得分变成了3，此时该店铺出系统，但是由于当前订单，得分再加2，变为5，如果这时才去判断与3的关系，显然不会出系统，也不会进系统，即保持原状态，但正确的结果应该是前者，即已经出系统了，且再加上2，等于5，也不会入系统。

代码

#include
using namespace std;
#define PII pair 
const int N = 100100;
int n, m , T, ts, id, ans;
vector  v;
int pretime[N], s[N], in[N];
int main()
{
	cin >> n >> m >> T; 
	for (int i = 0;i > ts >> id;
		v.push_back ({ts, id});
	}
	
	sort (v.begin (), v.end ());
	
	for (int i = 0;i  5) in[id] = 1;
//		else if (s[id]