1.27学习总结

今天做了些队列的题：
1.逛画展（单调队列）
2.打印队列 Printer Queue（优先队列）
3.[NOIP2010 提高组] 机器翻译(模拟队列)
4.求m区间内的最小值(单调队列板子题)
5.日志统计(滑动窗口，双指针)

总结一下：单调队列使用STL的deque进行模拟，也可以用数组和双指针(head,tail)，有两种操作，删头和去尾，实现一个区间内单调增或减的队列，经典的例题是滑动窗口，在用单调队列做题时，尽量队列内存的是索引，而不是这个数据本身

优先队列（堆）可用于求区间最值，数据较大的时候容易TLE

逛画展https://www.luogu.com.cn/problem/P1638

题目描述

博览馆正在展出由世上最佳的 �m 位画家所画的图画。

游客在购买门票时必须说明两个数字，�a 和 �b，代表他要看展览中的第 �a 幅至第 �b 幅画（包含 �,�a,b）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 �,�a,b，数据保证一定有解。

若存在多组解，输出 �a 最小的那组。

输入格式

第一行两个整数 �,�n,m，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

第二行包含 �n 个整数 ��ai​，代表画第 �i 幅画的名师的编号。

输出格式

一行两个整数 �,�a,b。

输入输出样例

输入 #1复制

12 5
2 5 3 1 3 2 4 1 1 5 4 3

输出 #1复制

2 7

说明/提示

数据规模与约定

• 对于 30%30% 的数据，有 �≤200n≤200，�≤20m≤20。
• 对于 60%60% 的数据，有 �≤105n≤105，�≤103m≤103。
• 对于 
• 100%100% 的数据，有 1≤�≤1061≤n≤106，1≤��≤�≤2×1031≤ai​≤m≤2×103。
• 思路：当还没有满足条件的时候一直入队，直到情况满足的时候，开始从头出队，直到情况未满足，找到所有可能的情况，并取出最小值

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int hash_count[20005];
int main()
{deque<int>q;int m,n;cin>>m>>n;int t=0;int min_length=m+2,l=0,r=m-1;for (int i=0;i<m;++i){cin>>a[i];if (hash_count[a[i]]==0)t++;hash_count[a[i]]++;q.push_back(i);while (t==n)//2 5 3 1 3 2 4 1 1 5 4 3{if (min_length>q.back()-q.front()){min_length=q.back()-q.front();l=q.front(),r=q.back();}hash_count[a[q.front()]]--;if (hash_count[a[q.front()]]==0)t--;q.pop_front();}}cout<<l+1<<" "<<r+1;
}

求m区间内的最小值https://www.luogu.com.cn/problem/P1440

题目描述

一个含有 �n 项的数列，求出每一项前的 �m 个数到它这个区间内的最小值。若前面的数不足 �m 项则从第 11 个数开始，若前面没有数则输出 00。

输入格式

第一行两个整数，分别表示 �n，�m。

第二行，�n 个正整数，为所给定的数列 ��ai​。

输出格式

�n 行，每行一个整数，第 �i 个数为序列中 ��ai​ 之前 �m 个数的最小值。

输入输出样例

输入 #1复制

6 2
7 8 1 4 3 2

输出 #1复制

0
7
7
1
1
3 

说明/提示

对于 100%100% 的数据，保证 1≤�≤�≤2×1061≤m≤n≤2×106，1≤��≤3×1071≤ai​≤3×107。

思路：模拟一个单调增的队列，队内没有的时候入队，有元素的时候判断，当前队尾元素是否小于将要入队的元素，如果不小于，那么队尾出队，直到找到一个小于的数或者队列空

#include <bits/stdc++.h>
using namespace std;
int a[2000005];
int main()
{int n,m;scanf("%d%d",&n,&m);deque<int>q;for (int i=0;i<n;++i){int x;scanf("%d",&x);a[i]=x;if (q.empty())printf("0\n");else printf("%d\n",a[q.front()]);while (!q.empty() && x<a[q.back()])q.pop_back();q.push_back(i);if (i-m==q.front())q.pop_front();}
}

日志统计https://www.luogu.com.cn/problem/P8661

题目描述

小明维护着一个程序员论坛。现在他收集了一份“点赞”日志，日志共有 �N 行。其中每一行的格式是 ts id，表示在 ��ts 时刻编号 ��id 的帖子收到一个“赞”。

现在小明想统计有哪些帖子曾经是“热帖”。如果一个帖子曾在任意一个长度为 �D 的时间段内收到不少于 �K 个赞，小明就认为这个帖子曾是“热帖”。

具体来说，如果存在某个时刻 �T 满足该帖在 [�,�+�)[T,T+D) 这段时间内（注意是左闭右开区间）收到不少于 �K 个赞，该帖就曾是“热帖”。

给定日志，请你帮助小明统计出所有曾是“热帖”的帖子编号。

输入格式

第一行包含三个整数 �N、�D 和 �K。

以下 �N 行每行一条日志，包含两个整数 ��ts 和 ��id。

输出格式

按从小到大的顺序输出热帖 ��id。每个 ��id 一行。

输入输出样例

输入 #1复制

7 10 2  
0 1  
0 10    
10 10  
10 1  
9 1
100 3  
100 3  

输出 #1复制

1  
3  

说明/提示

对于 50%50% 的数据，1≤�≤�≤10001≤K≤N≤1000。

对于 100%100% 的数据，1≤�≤�≤1051≤K≤N≤105，0≤��,��≤1050≤id,ts≤105。

思路：双指针+滑动窗口的做法，先按照时间排序。直到满足时间条件的时候，开始消除点赞数

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
struct Node{int time;int id;
};
struct Node  a[N];
int nums[N];//记录每个id的点赞数 
int flag[N];//记录是热评的 	
bool cmp(Node &a,Node &b)
{if (a.time!=b.time)return a.time<b.time;else if (a.time==b.time)return a.id<b.id;
}
int main()
{int n,d,k;cin>>n>>d>>k;	for (int i=0;i<n;++i)cin>>a[i].time>>a[i].id;sort(a,a+n,cmp);for (int i=0,j=0;i<n;++i){nums[a[i].id]++;while (a[i].time-a[j].time>=d){nums[a[j].id]--;j++;}if (nums[a[i].id]>=k)flag[a[i].id]=1;}for (int i=0;i<N;++i){if (flag[i])cout<<i<<endl;}
}

机器翻译https://www.luogu.com.cn/problem/P1540

题目描述

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有 �M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 �−1M−1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 �M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为 �N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入格式

共 22 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 �,�M,N，代表内存容量和文章的长度。

第二行为 �N 个非负整数，按照文章的顺序，每个数（大小不超过 10001000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出格式

一个整数，为软件需要查词典的次数。

输入输出样例

输入 #1复制

3 7
1 2 1 5 4 4 1

输出 #1复制

5

说明/提示

样例解释

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

1. 1：查找单词 1 并调入内存。
2. 1 2：查找单词 2 并调入内存。
3. 1 2：在内存中找到单词 1。
4. 1 2 5：查找单词 5 并调入内存。
5. 2 5 4：查找单词 4 并调入内存替代单词 1。
6. 2 5 4：在内存中找到单词 4。
7. 5 4 1：查找单词 1 并调入内存替代单词 2。

共计查了 55 次词典。

数据范围

• 对于 10%10% 的数据有 �=1M=1，�≤5N≤5；
• 对于 100%100% 的数据有 1≤�≤1001≤M≤100，1≤�≤10001≤N≤1000。

思路：队未满，开始入队，并且计数器要加1，队满开始出队和入队，计数器也加一

#include <bits/stdc++.h>
using namespace std;
int main()
{int m,n,cnt=0;cin>>m>>n;queue<int>q;//m是内存队列的长度最多等于m//这题主要难在找，用队列形成进去很简单int ans[1001];memset(ans,0,sizeof(ans));for (int i=0;i<n;++i){int x;cin>>x;if (ans[x]==0 && q.size()<m){q.push(x);ans[x]=1;	cnt++;}else if (ans[x]==1)continue;else if (ans[x]==0 && q.size()==m){ans[q.front()]=0;q.pop();	ans[x]=1;q.push(x);cnt++;}	}cout<<cnt; 
}

打印队列 Printer Queuehttps://www.luogu.com.cn/problem/UVA12100

学生会里只有一台打印机，但是有很多文件需要打印，因此打印任务不可避免地需要等待。有些打印任务比较急，有些不那么急，所以每个任务都有一个1～9间的优先级，优先级越高表示任务越急。

打印机的运作方式如下：首先从打印队列里取出一个任务J，如果队列里有比J更急的任务，则直接把J放到打印队列尾部，否则打印任务J（此时不会把它放回打印队列）。 输入打印队列中各个任务的优先级以及所关注的任务在队列中的位置（队首位置为0），输出该任务完成的时刻。所有任务都需要1分钟打印。例如，打印队列为{1,1,9,1,1,1}，目前处于队首的任务最终完成时刻为5。

输入T 接下来T组数据 每组数据输入N，TOP。接下来N个数，TOP代表队列首

Translated by @HuangBo

输入输出样例

输入 #1复制

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

输出 #1复制

1
2
5

思路：用优先队列和普通队列存值，然后按照优先队列的出队顺序找到队列对应的值出队

#include <bits/stdc++.h>
using namespace std;
struct node{int x;int id;
}x2;
priority_queue<int>q;
queue<node>p;
int main()
{int t;cin>>t;while (t--){int m,n;cin>>m>>n;for (int i=0;i<m;++i){int l;cin>>l;q.push(l);p.push(node{l,i});}int tot=0;while (!q.empty()){int x1=q.top(); q.pop();while (x2=p.front(),x2.x!=x1){p.pop();p.push(x2);	}p.pop();tot++;if (x2.id==n){cout<<tot<<endl;break;}}while (!p.empty())p.pop();while (!q.empty())q.pop();} 
}