队列安排
- 首先，这道题是对一个数列进行频繁的插入和删除操作，这和链表正好是吻合的，是用链表来做无疑了。
（可是我当时并没有想到，还是经验太少了） - 明白要用链表来做之后，我打算用STL中的List来做。
- 那么就会用到很多前置知识，我唯独缺少了这个：
list.insert(it, n)可以返回n插入后所在位置上的迭代器。
什么意思呢？
迭代器：可以理解为用于访问STL容器上某一个元素的一种指针。
那么pos = list.insert(it, n)就可以用pos得到n被插入后所在位置的指针。
换句话来说，就是用pos指向n被插入后所在位置。
这道题可以这样操作：- 定义一个迭代器数组
pos[N],里面用来储存 1到n 所在位置的迭代器;
也就是用pos[N]指向1到n所有元素在List上的位置。 - 这样写：
pos[n] = list.insert(it, n);;pos[n]就会 得到 以迭代器的类型 返回 n被插入位置上的迭代器。.
也就是pos[n]会指向n在List上的位置！！
这样的话就可以用pos[n]直接访问n在List的位置，进行插入和删除操作。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
list<int>s;
list<int>::iterator pos[N];
list<int>::iterator it;
//用来判断当前元素是否在 list 内
bool st[N];
int main(){
// freopen("ttt.in", "r", stdin);
// freopen("ttt.out", "w", stdout);
memset(st, 1, sizeof(st));
s.push_back(1);
pos[1] = s.begin();
int n; cin >> n;
for(int i = 2; i <= n; i ++){
int a, b;
scanf("%d%d", &a, &b);
it = pos[a];
//右边 ,否则左边
if(b) it ++;
//插入
pos[i] = s.insert(it, i);
}
int m; cin >> m;
for(int i = 1; i <= m; i ++){
//输入要出来的元素
int a; cin >> a;
//如果这个元素还在List里面
if(st[a]){
//用于删除某节点
s.erase(pos[a]);
st[a] = 0;
}
}
for(it = s.begin(); it != s.end(); it ++)
printf("%d ", *it);
puts("");
return 0;
}
/*
这是find()，可以直接找到n的位置
// d.push_back(1);
// d.push_back(3);
// it = find (d.begin(), d.end(), 9);
it --;
printf("%d ", *it);
// cout << *it;
*/
序列合并
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//大根堆
priority_queue<int>q;
int a[N], b[N], ans[N];
int main(){
int n;
//题目说了这里是严格递增的，我们就不需要额外排序了
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++) scanf("%d", &b[i]);
for(int i = 1; i <= n; i ++){//a的迭代器
for(int j = 1; j <= n; j ++){//b的迭代器
int sum = a[i] + b[j];
//一旦还不够就先加入
if(q.size() < n) q.push(sum);
else{
//够了的话 ,就只要把那些比当前最大的数要小的放进来就好了
if(q.top() > sum){
q.pop();
q.push(sum);
}
//如果不满足条件就说明这个元素比当前所有的元素都要大，不管他
//这里的break是对j的循环生效的，
//也就是说，当前i的情况下再去遍历后面的j已经没有意义了
//因为b数组时单调递增的，后面的数也是铁定大于当前a[i] + b[j]的，一定是会被淘汰的。
//于是开始下一个i
//到后面基本上是不会进行什么操作了的，因此实际时间应该非常低才对。
else break;
}
}
}
//反向输出
for(int i = n; i >= 1; i --){
ans[i] = q.top();
q.pop();
}
for(int i = 1;i <= n; i ++) printf("%d ",ans[i]);
return 0;
}
扫描
题目链接
不多解释了，这就是低配的滑动窗口嘛，老熟悉了我……
就当是第五刷了。前四刷链接
#include<bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
deque<int>q;
int a[N];
int main(){
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++){
//首先当然是维护队列的单调性啦!
while(!q.empty() && a[i] > a[q.back()]) q.pop_back();
if(!q.empty() && q.front() < i - k + 1) q.pop_front();
q.push_back(i);
if(i >= k) printf("%d
", a[q.front()] );
}
return 0;
}
约瑟夫问题
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int>table;//定义一个数组模拟圆桌
int n,m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) table.push_back(i);
//如果还没空掉那就操作
//一开始的指针位置，从0开始数数
int pos = 0;
while(!table.empty()){
//首先是找到当前的指针位置 (以确定删除的位置)
pos = (pos + m - 1) % table.size();
//将其输出
printf("%d ", table[pos]);
//出队
table.erase(table.begin() + pos);
}
return 0;
}