线性数据结构&堆

[刷题记录]线性数据结构&二叉堆

这两天刷了一些简单的线性数据结构和二叉堆（优先队列）的题目，学会了一些STL的骚操作，简单记录一下。

洛谷 P1168 中位数

题意

  • 给出一个长度为$N$的非负整数序列$Ai$，对于所有$1 \leq k \leq \frac{N+1}{2}$，输出$A_1, A_3, …, A{2k - 1}$的中位数。即前$1,3,5,…$个数的中位数。

Sample Input

1
2
7
1 3 5 7 9 11 6

Sample Output

1
2
3
4
1
3
5
6

数据范围：$N\leq 1e5$

思路&题解

  • 思考1：首先我们发现如果这个序列是有序的，那就太简单了，直接用数组存储，然后每隔一个数用下标访问输出中间那一个数就好了，因此想到每输入两个数的时候sort一次，复杂度是$O(n^2logn)$然而数据范围是100000，必爆炸，因此考虑其他做法；
  • 思考2：有没有可能边输入边排序呢？当然可以，我们可以使用priority_queue，堆插入的复杂度只有$O(logn)$，然而，排序是解决了，但怎么访问中位数呢？我们知道，优先队列只能访问队首元素，好像行不通。。
  • 思考3：又想在输入的同时排序，又想能够访问元素，对了，我们可以使用最原始的$vector$或者数组模拟这样的操作啊，因为我们有lower_bound这样的骚操作可以达到边输入边维护有序的操作，就像在模拟插入排序一样，OK，那么此题解决。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
vector<int> a; 
int main(){
    int n,x;
    cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		if(!a.empty()){ //下面是通过二分查找来维护vector有序
			int pos = lower_bound(a.begin(),a.end(),x)-a.begin();
			a.insert(a.begin()+pos,x);
		//	cout<<pos<<" ";	
		}else a.push_back(x);
		if((i+1)%2==1) cout<<a[(i+1)/2]<<endl;
	}
	return 0;
}

洛谷 P1631 序列合并

题意

  • 有两个长度都是$N$的序列$A$和$B$，在$A$和$B$中各取一个数相加可以得到$N^2$个和，求这$N^2$个和中最小的$N$个。

    Sample Input

    1
    2
    3
    3
    2 6 6
    1 4 8

    Sample Output

    1
    3 6 7

    数据范围：$1\leq N \leq 1e5$

思路&题解

  • 思考1：总共$N^2$个数，我枚举出来，然后每次都push进一个小根堆里，最后输出前$N$个不就行了吗，于是看了一眼数据范围，很明显这题暴力$O(N^2)$是拿不了满分的，然而试了一下下，骗了70分,我惊了，居然还能MLE；

    image.png

    骗分代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include<bits/stdc++.h>
    using namespace std;
    priority_queue<int,vector<int>,greater<int> > pq;
    int a[100005],b[100005];
    int main(){
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=1;i<=n;i++) cin>>b[i];
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){ // 
    			pq.push(a[i]+b[j]);
    		}
    	}
    	for(int i=1;i<=n;i++){
    		cout<<pq.top()<<" ";
    		pq.pop();
    	}
    	return 0;
    }

  • 思考2：发现这个题输入是已经排好序的了，于是想了多种办法但都处理不好每次输出最小的数这样的操作，于是看了题解，看到一个神犇绝妙的解法，只需要在上述代码上加一点点小小的优化（剪枝）就好了：内部for循环改为for(int j=1;j<=n&&(i-1)*(j-1)<=n;j++)就可以了。那么为什么要加一句(i-1)*(j-1)<=n呢？

    数学证明：对于两个有序序列$A$和$B$，如果此时想要把$Ai+B_i$ push进小根堆中,而$i$和$j$满足$(i-1)*(j-1)>N$，那么这个数一定已经不是前N小的数了，因为对于这两个序列来说，$1…i-1$和$1…j-1$所能构成的和的总数也就是$(i-1)*(j-1)$个，**而且最大值是$A{i-1}+B{i-1}$**，显然$A{i-1}+B{i-1}<A{i}+B_{i}$，因此算法成立。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > pq;
int a[100005],b[100005];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n&&(i-1)*(j-1)<=n;j++){ //key 
			pq.push(a[i]+b[j]);
		}
	}
	for(int i=1;i<=n;i++){
		cout<<pq.top()<<" ";
		pq.pop();
	}
	return 0;
}

洛谷 P2827 蚯蚓

题意

  • 有若干蚯蚓，每个蚯蚓有一个长度，每一秒切开最长的那一只蚯蚓，其他蚯蚓每秒长度+q，如此重复若干秒，要求输出每次切割的蚯蚓的长度和最终每只蚯蚓的长度（从大到小排列）
  • 更具体的IO和数据范围点开链接看题

思路&&题解

  • 思考1：这还不简单，把蚯蚓存入一个大根对里，每次取根部元素切开然后再push回去，可是，如何处理每次蚯蚓的生长呢？难不成每次都遍历一遍然后+=q？看了一眼数据范围，必爆炸，于是放弃；

  • 看题解后思考：使用三个queue，q1、q2、q3，q1用来存储原始的蚯蚓，q2存放每次被切蚯蚓的较长段，q3存放每次被切蚯蚓的较短段，q1需要先排好序（单调递减），这样的话，q2和q3也就都满足单调递减了，为什么呢？

    因为先切的蚯蚓被分出来的两段一定大于后切的蚯蚓被分出来的两段（较长段大于较长段，较短段大于较短段），这是因为从先切的蚯蚓开始到后切的蚯蚓结束，流逝的时间是相同的，即增长的长度是相同的，因此只要满足q1单调递减就一定能使得q2和q3单调递减；

  • 如何处理增长？因为每过一秒，除了被切蚯蚓之外的蚯蚓都会+=q，逆向思维，等价于被切蚯蚓-=q，但每次切的时候还是要按照真实长度（即增长过后的长度）切割，那么如何处理这一过程呢？可以定义一个数tim用来记录时间过去了多少（每次切割时tim+=q）。这样，我们存放在q1、q2、q3队列中的长度都是假想的“没有增长的长度”，每次从这三个队列中中取出最长的蚯蚓时，只需要再+tim就可以复现真实的蚯蚓长度，切完之后再把切完的两段分别-=tim+q（更好的是先执行tim+=q更新增长长度，再两段分别-tim）就可以达到放回去的时候相当于被切蚯蚓缩短了q的效果。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f;
ll n,m,q,t,ans2[9000005],ans[9000005];
double u,v;
priority_queue<ll> q1;
queue<ll> q2,q3;

ll getmax(){ //从三个队列中取出最长段，对应的队列执行pop操作
	ll max1=-inf,max2=max1,max3=max1;
	if(!q1.empty()) max1 = q1.top();
	if(!q2.empty()) max2 = q2.front();
	if(!q3.empty()) max3 = q3.front();
	if(max1>=max2&&max1>=max3) {
		q1.pop();
		return max1;
	}else if(max2>=max1&&max2>=max3){
		q2.pop();
		return max2;
	}else{
		q3.pop();
		return max3;
	}
}

int main(){
	cin>>n>>m>>q>>u>>v>>t;
	ll x;
	for(ll i=1;i<=n;i++){
		cin>>x;
		q1.push(x); //大根堆，满足q1单调减
	}
	ll tim=0;
	for(ll i=1;i<=m;i++){ // 遍历每一秒的操作
		ans[i] = getmax()+tim; //变为真实长度（顺便记录每次切割的长度）
		ll t1=ans[i]*u/v; 
		ll t2=ans[i]-t1;
		tim+=q; //更新时间
		if(t1<t2) swap(t1,t2); //较长段放入q2，另一段放入q3
		q2.push(t1-tim); //相当于缩短了q
		q3.push(t2-tim);
	}
	ll cnt=0;
	while(!q1.empty()||!q2.empty()||!q3.empty()){ //最终每一段蚯蚓的长度
		ans2[++cnt]=getmax()+tim;
	}
	for(ll i=t;i<=m;i+=t) cout<<ans[i]<<" ";
	cout<<endl;
	for(ll i=t;i<=cnt;i+=t) cout<<ans2[i]<<" ";
	return 0;
}

洛谷 P1503 鬼子进村

题意

  • 有$n$个用地道相连的房子，第$i$个与第$i-1$和$i+1$个相连，随后有$m$个消息传过来，分别是以下三者中的某一种：
    1. D x：鬼子将 x 号 房子摧毁了，地道被堵上
    2. R：村民将鬼子上一个被摧毁的房子修复了
    3. Q x：有一名士兵被围堵在了x号房子中

现在要求输出每一个被围堵的士兵能够到达的房子有几个。

Sample Input

1
2
3
4
5
6
7
8
9
10
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

Sample Output

1
2
3
4
1
0
2
4

数据范围：$n,m\leq50000$

思路&题解

  • 思考1：一开始想到链表，可是R操作比较难搞，但这个R不就是一个栈吗？于是考虑栈，但栈无法遍历每一个元素，因为我们要求每个士兵所在的区间，于是还是考虑使用$vector$模拟栈的操作（push_back和pop_back），还能遍历每个元素，岂不美哉；
  • 思考2：发现如果使用$vector$，那么复杂度会有点高，因为每次求每个士兵的区间时需要对$vector$排序（按题目输入来看，它本身是无序的），看了看数据范围，感觉还OK，因此我再开一个$vector$，在每次需要查询区间的时候把原来的$vector$赋值给新$vector$然后对新$vector$排序，再对新$vector$遍历求区间就好了，复杂度应该会降不少；
  • 至于怎么找士兵能到达几个房子，这个比较简单，我是直接遍历一遍排序好的$vector$，记录士兵所在区间，然后直接区间尾 - 区间头 - 1就好了，注意一下头部和尾部的处理。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
vector<int> vec1,vec2;
int n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		char c;
		cin>>c;
		if(c=='D'){ //摧毁房子
			int x;
			cin>>x;
			vec1.push_back(x); //压入vector栈中
		}
		if(c=='Q'){
			int x;
			cin>>x;
			vec2.assign(vec1.begin(),vec1.end()); //拷贝一份
			sort(vec2.begin(),vec2.end()); //排序
			vector<int>::iterator it;
			int pos=0,end=n;
			bool f=true;
			for(it=vec2.begin();it!=vec2.end();it++){ //找答案
				if((*it)==x){
					cout<<0<<endl;
					f=false;
					break;
				}else if((*it)>x){
					cout<<*it-pos-1<<endl;
					f=false;
					break;
				}pos=*it;
			}
			if(f) cout<<end-pos<<endl;
		}
		if(c=='R'){
			vec1.pop_back();
		}
	}
	return 0;
}
  • emm题目还是有点挑战性的，具体收获如下
    1. 要善于发现题目中隐含的条件（如：单调性 等）以优化时间复杂度；
    2. 善于利用$vector$模拟一些线性数据结构（如：栈，小根堆也可），毕竟$vector$可以通过下标或者$iterator$遍历每个元素；