首页 > ACM题库 > HDU-杭电 > HDU 2835-Operating system[解题报告]HOJ
2014
02-17

HDU 2835-Operating system[解题报告]HOJ

Operating system

问题描述 :

As a CS student, operating system is an important lesson. Today, let’s think about the cache’s working mode. All object accesses go through the cache, so every time an object is accessed, it must be inserted into the cache if it was not already there. If the cache is full, you must take out a object which is already in the cache . All objects are of equal size, and no writes occur in the system, so a cached object is always valid. When the system starts, the cache is empty. To make cache works efficiently, we need find the optimal replacement algorithm. Optimality here means minimizing the number of times an object is read into the cache.

输入:

There are several test cases in the input.

Each test case begins with three integers(C,N,B), separated by single spaces, telling you how many objects fit in the cache, 0 < C ≤ 10000, how many different objects are in the system, C ≤ N ≤ 100000, and how many accesses, 0 ≤ B ≤ 100000, will occur. The following line contains B integers between 0 and N-1 (inclusive) indicating what object is accessed.

输出:

There are several test cases in the input.

Each test case begins with three integers(C,N,B), separated by single spaces, telling you how many objects fit in the cache, 0 < C ≤ 10000, how many different objects are in the system, C ≤ N ≤ 100000, and how many accesses, 0 ≤ B ≤ 100000, will occur. The following line contains B integers between 0 and N-1 (inclusive) indicating what object is accessed.

样例输入:

1 2 3
0 1 0
2 2 3
0 1 0

样例输出:

3
2

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x7fffffff
#define LL long long
#define LD long double
#define PII pair<int,int>
#define x first
#define y second
#define pb push_back
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

#define N 100010
int last[N],link[N],next[N],ord[N];

struct heap {

 vector<int> h,pos;
 int n;

 heap() : h(N),pos(N),n(0) {}

 inline int cmp(int p,int q) {
 p=h[p],q=h[q];
 return next[p]>next[q];
 }

 void swap(int p,int q) {
 if (p==q) return;
 int &pos1=pos[h[p]],
 &pos2=pos[h[q]];
 std::swap(h[p],h[q]);
 std::swap(pos1,pos2);
 }

 int goup(int x) {
 while (x>1 && cmp(x,x/2)) {
 swap(x,x/2);
 x/=2;
 }
 return x;
 }

 void godown(int x) {
 loop:
 if (x*2>n) return;
 int y=x*2;
 if (y+1<=n && cmp(y+1,y)) y++;
 if (cmp(y,x)) {
 swap(x,y);
 x=y;
 } else return;
 goto loop;
 }

 void deln() {
 pos[h[n]]=0;
 h[n]=0;
 n--;
 }

 void pop() {
 swap(1,n);
 deln();
 godown(1);
 }

 void pop(int x) {
 x=pos[x];
 swap(x,n);
 deln();
 x=goup(x);
 godown(x);
 }

 void push(int x) {
 n++;
 h[n]=x;
 pos[x]=n;
 goup(n);
 }

 int top() {return h[1];}
 int size() {return n;}
 int find(int x) {return pos[x]>0;}
};

int main() {
 //freopen("data.txt","r",stdin);
 int c,n,b;
 while (~scanf("%d%d%d",&c,&n,&b)) {
 fill(last,last+N,0);
 fill(link,link+N,INF);
 for (int i=1,k;i<=b;i++) {
 scanf("%d",ord+i),ord[i]++;
 if (last[ord[i]]) {
 link[last[ord[i]]]=i;
 }
 last[ord[i]]=i;
 }

 heap h;
 int ans=0;
 for (int i=1;i<=b;i++) {
 if (!h.find(ord[i])) {
 if (h.size()==c) h.pop();
 ans++;
 } else {
 h.pop(ord[i]);
 }
 next[ord[i]]=link[i];
 h.push(ord[i]);

 //printf("i=%d push(%d,%d) |h|=%d ans=%d\n",i,ord[i]-1,next[ord[i]],sz(h),ans);
 }
 printf("%d\n",ans);
 }
 return 0;
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮