碳之狼

用户名：1024650038

访问量：8491

签　名：

现在的我什么都做不到

等　　级
排　　名	664
经　　验	4015
参赛次数	0
文章发表	17
年　　龄	18
在职情况	学生
学　　校	东莞理工学院
专　　业	计算机类

　　自我简介：

TA的其他文章

蓝桥杯2019年第十届真题-完全二叉树的权值-题解（C++代码）
浏览：324

蓝桥杯2019年第十届真题-等差数列-题解（C++代码）辗转相除求最大公约数
浏览：382

蓝桥杯2019年第十届真题-外卖店优先级-题解（C++代码）时间复杂度不高
浏览：526

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （Java代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

蓝桥杯2019年第十届真题-外卖店优先级-题解（C++代码）时间复杂度不高

　　作者: 碳之狼　　　　发表时间：2021-02-06 17:52:25 浏览：526　|　评论：0　

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

问题可以离散处理，不必遍历T个时刻。先将订单按照时间顺序排序，再遍历每一个收到订单的时间点，此时该商户的缓存减去当前时间与上一个收到订单的时间的间隔，再加上2，再分析判断一下纳入/移除优先缓存的情况即可，时间复杂度是O(m+nlog(n))
如果把vector换成数组，加上快读还会快很多
```cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
bool cmp(const vector<int>& a, const vector<int>& b) {
	return a[0] < b[0];
}
int main()
{
	int n, m, t;
	cin >> n >> m >> t;
	vector<vector<int>> v(m, vector<int>(2));
	vector<int> ans(n + 1);
	vector<int> time(n + 1);
	vector<bool> book(n + 1);
	for (int i = 0; i < m; i++) cin >> v[i][0] >> v[i][1];
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < m; i++) {
		int sum = v[i][0] - time[v[i][1]] - 1;
		if (time[v[i][1]] == 0 || sum <= 0) time[v[i][1]] = v[i][0];
		else {
			ans[v[i][1]] = ans[v[i][1]] > sum ? ans[v[i][1]] - sum : 0;
			time[v[i][1]] = v[i][0];
		}
		//如果之前纳入过优先缓存，在当前时刻已经<=3则移除
		if (book[v[i][1]] && ans[v[i][1]] <= 3) book[v[i][1]] = false;
		ans[v[i][1]] += 2;
		if (ans[v[i][1]] > 5) book[v[i][1]] = true;
	}
	for (int i = 1; i <= n; i++) {
		if (time[i] == 0) continue;
		int sum = t - time[i];
		ans[i] = ans[i] > sum ? ans[i] - sum : 0;
		if (book[i] && ans[i] <= 3) book[i] = false;
	}
	int res = 0;
	for (int i = 1; i <= n; i++) res += book[i] ? 1 : 0;
	cout << res << endl;
	return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

碳之狼

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （Java代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

【蟠桃记】（C语言代码）

【偶数求和】（C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

蓝桥杯2019年第十届真题-外卖店优先级-题解（C++代码）时间复杂度不高

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

程序员的表白（C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1013题解

矩形面积交（C++代码）

程序员的表白（C语言代码）

碳之狼

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （Java代码）

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

【蟠桃记】 （C语言代码）

【偶数求和】 （C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

蓝桥杯2019年第十届真题-外卖店优先级-题解（C++代码）时间复杂度不高

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

程序员的表白 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

【魔板】 （C++代码）(时间超限，希望会的帮我改正一下)

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1013题解

矩形面积交 （C++代码）

程序员的表白 （C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

【蟠桃记】（C语言代码）

【偶数求和】（C++代码）

　　评论区

程序员的表白（C语言代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

矩形面积交（C++代码）

程序员的表白（C语言代码）