自动搬运

查看原文

来自洛谷，原作者为

	wjx38223 一！二！

搬运于2025-08-24 22:41:28，当前版本为作者最后更新于2023-11-20 18:37:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路分析

首先，对于每一家店，我们考虑到需要从时间 $1$ 开始，一直遍历到时间 $T$，如果有记录，那么 优先级 加上 $2$，否则，优先级 减去 $1$，对于每一个节点，判断这家店 是否在优先推荐中

• 优化1： 那么此时，由于我们把有记录和没有记录的时间点都遍历了一遍，自然浪费时间，所以，我们可以只 查找这家店有记录的时间点，没有用的点，我们用减法就能求出

• 优化2：我们需要按顺序找到每一个有记录的节点，这就需要排序，那么我们来想 一种先进先出并且排序的东西 ，所以， 优先队列 就是一个好选择，对于每一家店，我们都为其准备一个 优先队列 来存储时间点

注意一点的是： 如果在本时刻，该店的优先级 $>5$，在优先推荐中为真；如果在本时刻，在优先推荐中为真，且该店的优先级 $≤3$，在优先推荐中为假。

代码展示

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	priority_queue<int,vector<int>,greater<int>> h[100010]; //为每一家店创造一个优先队列（小顶对）
	int n, m, t;
	cin >> n >> m >> t;
	for(int i = 1; i<=m; i++){
		int x, y;
		cin >> x >> y;
		h[y].push(x);//把时间点存入这家店的队列中
	}
	int cnt = 0;
	for(int i = 1; i<=n; i++){
		int pri = 0; //“优先级”
		int lastget = 0; //上一次订单的时间
		bool in = false; //是否在“优先推荐”中
		while(!h[i].empty()){
			int x = h[i].top(); //订单时间
			h[i].pop();
			if(lastget!=x) pri-=(x-lastget-1);//如果不是同一个时间点多个订单的话，减去没有订单的那些时间需要减去的“优先级”
			if(pri<0) pri = 0; //可能小于零，设置成零
			if(in&&pri<=3) in = false; //如果在推荐里，但是此时“优先级”小于等于3，踢出推荐中
			pri+=2; //拿到两点“优先级”
			lastget = x; //更新上一次时间
			if(pri>5) in = true; //如果此时“优先级”大于3，踢出推荐中
		}
      		//注意的是，这里需要先判断是否被踢出推荐，然后再加上2，
      
      		//因为加入的条件是大于5，退出的条件是小于等于3，如果此时小于等于3了，但是加上2之后不小于3了，按照程序，符合“在推荐中+没有小于等于3”，不会被踢出去，
      		//但是由于在这些空余的时间里，已经出了推荐榜，如果再进，需要大于5，此时没有达到在加入的条件，没有在推荐榜中
      
      		//这里，由于要看的是时间T，但是T有可能不是最后一次收到订单的时间，需要额外判断，方法同上
		if(lastget!=t) pri-=(t-lastget);
		if(in&&pri<=3) in = false;
		if(in){
			cnt++;
		}
	} 
	cout << cnt;
	return 0;
}