JSOI2010 缓存交换

wjh15101051's space

卧薪尝胆，厚积薄发。

JSOI2010 缓存交换

Date: Thu Oct 18 15:02:06 CST 2018

In Category: NoCategory

Description：

缓存容量为 $m$ ，现在要依次访问 $n$ 个位置，访问前必须先把它加入缓存，如果空间不够就拿走一个，问每次拿走哪个可以使得加入缓存的操作尽量少。

$1\leqslant n\leqslant10^5$

Solution：

正解是每次把下一次出现位置最靠后的贪心的从缓存中拿走，这样用一个堆维护就可以了。

想一想好像挺显然的，因为对于两个如果 $A$ 在 $B$ 下一次出现之前出现了好几次的话把它留下来显然更优。

贪心的思路之一，看两个元素之间谁更优，从而推出全部。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<set>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int a[MAXN];

int nxt[MAXN];

map<int,int> last;

map<int,bool> exist;

struct cmp

{

	bool operator () (int a,int b)

	{

		return nxt[a] < nxt[b];

	}

};

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

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

	{

		if(last.find(a[i]) == last.end())nxt[i] = n + 1;

		else nxt[i] = last[a[i]];

		last[a[i]] = i;

	}

	int s = 0;

	int ans = 0;

	priority_queue<int,vector<int>,cmp> q; 

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

	{

		if(exist[a[i]])

		{

			q.push(i);

			continue;

		}

		if(s < m)

		{

			++s;

			exist[a[i]] = true;

			q.push(i);

			++ans;

		}

		else

		{

			if(!exist[a[i]])

			{

				exist[a[q.top()]] = false;

				q.pop();

				++ans;

				q.push(i);

				exist[a[i]] = true;

			}

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: 算法-贪心

wjh15101051