题目

链接：https://ac.nowcoder.com/acm/contest/28537/F
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

在学习Operating System的过程中，Glory遇到了这样一个问题，现在有一个大小为可以容纳N个页面的内存，硬盘内的内容被分成M个页面，用1~M来标识，一开始内存里没有任何页面，接下来用户会请求Q个页面，你需要设计一个置换算法，使得缺页发生的次数最少。缺页是指用户请求某个编号的页面，但这个页面没有在内存中的情况。发生缺页之后，你必须要把硬盘内对应的页面调入内存中，如果内存已满，你需要置换掉当前内存中的某个页面。

输入描述:
多组数据，请处理到输入结束。

每组数据，第一行为三个整数N，M，Q （0 < N，M，Q <= 50000）

接下来一行Q个数，表示用户请求的页面编号。
输出描述:
对于每组数据，输出一个数，表示最少的缺页次数。
示例1

输入
2 3 5

3 1 2 1 2

3 4 5

3 2 1 4 3
输出
3

4

题解

突破点一:目前我所知道的在一个容器中取最值的方法有

优先队列时间复杂度为logn;(适用于本道题目)
单调栈/队列时间复杂度为1;(适用于滑动窗口)

突破点二:使用贪心

贪心,对于要被替换的元素,找到一个下一个该元素距离这个位置最远的元素来进行替换

突破点三:

由于优先队列可以自定义排序,所以我打算在优先队列里面存放下标

卡了3个小时的点:(std为我写的.test为标程)

注意优先队列仅仅是一个共具,实际上起到判断作用的是数组…

在找到一个相同的值以后,本应该更新一下值,但是太麻烦,索性直接push一个新的值,这样就可以了掩盖掉之前陈旧的数据

代码

#include <iostream>

#include <stack>

#include <string>

#include <queue>

#include <cstring>

using namespace std;//我的打算是把数组放到前面,之后直接初始化.

const int MAX = 50005;

int a[MAX];

int being[MAX] = { 0 };

int next_[MAX];

int next_assist[MAX];

int ans = 0;

priority_queue<pair<int, int> >q;

int cnt;

void clear(priority_queue<pair<int, int> >& q)

{

	priority_queue<pair<int, int> >empty;

	empty.swap(q);

}

void init()

{

	ans = 0;

	clear(q);

	memset(a, 0, sizeof(a));

	memset(being, 0, sizeof(being));

	memset(next_assist, 0x7f, sizeof(next_assist));

	memset(next_, 0, sizeof(next_));

	cnt = 0;

}

int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	int N, M, Q;

	while (cin >> N >> M >> Q)

	{

		init();

		for (int i = 1; i <= Q; i++)

		{

			cin >> a[i];

		}

		for (int i = Q; i >= 1; i--)

		{

			next_[i] = next_assist[a[i]];

			next_assist[a[i]] = i;

		}

		cnt = 0;

		ans = 0;

		for (int i = 1; i <= Q; i++)

		{

			if (!being[a[i]] && ans >= N)

			{

				ans++;

				being[q.top().second] = 0;

				q.pop();

				q.push(pair<int, int>(next_[i], a[i]));

				being[a[i]] = 1;

			}

			else if (!being[a[i]] && ans < N)

			{

				cnt++;

				q.push(pair<int, int>(next_[i], a[i]));

				being[a[i]] = 1;

				ans++;

			}

            else

            {

                q.push(pair<int, int>(next_[i], a[i]));

            }

		}

		cout << ans << endl;

	}

}

巴特西

Operating System_via牛客网

题目

题目描述

输入描述:

输出描述:

输入

输出

题解

突破点一:目前我所知道的在一个容器中取最值的方法有

突破点二:使用贪心

突破点三:

卡了3个小时的点:(std为我写的.test为标程)

代码

最新文章

热门文章