UVA 11423 - Cache Simulator (树状数组)

题目链接

题目大意：模仿磁盘缓冲区的工作机制，给你n个不同size的（递增的）磁盘缓冲区，给你要访问的数据，根据LRU原则，问每个size的磁盘分别有多少次miss（数据没有在缓存中就是miss），

解题思路：因为数据最多有10^7，所以数据访问的序列最长也就是10^7。树状数组的每个位置代表的是访问序列的位置有没有数，因为如果之前的数在后面有访问到的话，那么这个数就应该在后面了，这样前面的那个数就应该不存在。做法：先将要访问的数据序列处理出来，放在队列中，并且找到每个数之前出现过的离它最近的那个位置。查询当前的位置和之前那个出现的位置之间有多少个数（假设dis个）；小于dis的cache的miss++，然后要记得删除树状数组之前的那个位置上的值。如果是没有出现过的数，那么miss肯定是要+1的。注意：每次state都要重新计算miss。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

const int N = 35;
const int maxn = 1e7 + 5;
#define lowbit(x) ((x)&(-x))

int n;
int Miss[N], Cache[N];
int C[maxn];
char str[N];

void add (int x, int v) {
    while (x < maxn) {

        C[x] += v;
        x += lowbit(x);
    }
}

int sum (int x) {
    int ret = 0;
    while (x > 0) {

        ret += C[x];
        x -= lowbit(x);
    }
    return ret;
}

struct Num {
    int value, pre;
    Num (int value , int pre) {
        this->value = http://www.mamicode.com/value;"hljs-keyword" style="color:rgb(249,38,114)">this->pre = pre;
    }
};
queue<Num> Q;
map<int, int> vis;

void init () {

    int b, y, k;
    memset (Miss, 0, sizeof(Miss));
    vis.clear();
    while (scanf ("%s", str) && str[0] != ‘E‘) {

        if (str[0] == ‘R‘) {
            scanf ("%d%d%d" , &b, &y, &k);
            for (int i = 0; i < k; i++) {
                Q.push(Num(b + y * i, vis[b + y * i]));
                vis[b + y * i] = Q.size();
            }
        } else if (str[0] == ‘A‘) {
            scanf ("%d", &b);
            Q.push(Num (b, vis[b]));
            vis[b] = Q.size();
        } else {
            Q.push(Num (-1, 0));
        }
    }
}

void solve () {

    init();
    memset (C, 0, sizeof (C));
    int cnt = 0;
    while (!Q.empty()) {

        if (Q.front().value >= 0) {

            add(cnt + 1, 1);
            if (Q.front().pre > 0) {

                int dis = sum(cnt + 1) - sum(Q.front().pre);    
//                printf ("%d %d %d %d\n", Q.front().value, cnt + 1, Q.front().pre, dis);
                for (int i = 0; i < n; i++) {
                    if (Cache[i] < dis)
                        Miss[i]++;
                    else
                        break;
                }    
                add(Q.front().pre, -1);
            } else {
                for (int i = 0; i < n; i++)
                    Miss[i]++;
            }
        } else {
            for (int i = 0; i < n - 1; i++)
                printf ("%d ", Miss[i]);
            printf ("%d\n", Miss[n - 1]);
            memset (Miss, 0, sizeof (Miss));
        }
        Q.pop();
        cnt++;
    }
}

int main () {

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

    solve();
    return 0;
};

UVA 11423 - Cache Simulator (树状数组)