这个题仔细一想可以直接贪心做,因为队列里下一个出现的早的一定最优。正确性显然。然后我只拿了50,我直接模拟另一个队列暴力修改最后一个点的nxt值,自然会T。但是其实不用修改,直接插入就行了前面的不影响后面的。然而只有80分,因为没有离散化。
题干:
Description在计算机中,CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时,则需要从主存里把数据调入Cache。此时,如果Cache容量已满,则必须先从中删除一个。 例如,当前Cache容量为3,且已经有编号为10和20的主存单元。 此时,CPU访问编号为10的主存单元,Cache命中。 接着,CPU访问编号为21的主存单元,那么只需将该主存单元移入Cache中,造成一次缺失(Cache Miss)。 接着,CPU访问编号为31的主存单元,则必须从Cache中换出一块,才能将编号为31的主存单元移入Cache,假设我们移出了编号为10的主存单元。 接着,CPU再次访问编号为10的主存单元,则又引起了一次缺失。我们看到,如果在上一次删除时,删除其他的单元,则可以避免本次访问的缺失。 在现代计算机中,往往采用LRU(最近最少使用)的算法来进行Cache调度——可是,从上一个例子就能看出,这并不是最优的算法。 对于一个固定容量的空Cache和连续的若干主存访问请求,聪聪想知道如何在每次Cache缺失时换出正确的主存单元,以达到最少的Cache缺失次数。Input输入文件第一行包含两个整数N和M(1<=M<=N<=100,000),分别代表了主存访问的次数和Cache的容量。 第二行包含了N个空格分开的正整数,按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。Output输出一行,为Cache缺失次数的最小值。Sample Input6 21 2 3 1 2 3Sample Output4HINT在第4次缺失时将3号单元换出Cache。SourceJSOI2010第二轮Contest2
代码:
#include#include #include #include #include #include #include using namespace std;#define duke(i,a,n) for(int i = a;i <= n;i++)#define lv(i,a,n) for(int i = a;i >= n;i--)#define clean(a) memset(a,0,sizeof(a))const int INF = 1 << 30;typedef long long ll;typedef double db;template void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x;}template void write(T x){ if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10);}struct node{ int nxt,w; bool operator < (const node &oth) const { return nxt < oth.nxt; }} a[200010];int num = 0,n,m,tot,ans = 0;int lst[200010];int vis[200010];int k[200010];priority_queue qu;int main(){ read(n); read(m);// cout< < = m) { node f = qu.top();// cout< <<" "< <