202006-2稀疏向量

题目

稀疏向量

题目截图:

image-20211202180655063

思路

60分答案

我的第一思路是开一个二维数组,相当于开了一个两行好多列的二维表(为什么说好多列呢?因为主要取决于你那个只有多大),然后数组下标就表示矩阵下标,然后将他们对应下标的值相乘再相加就能够实现题目要求的内容了。

代码

 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
/* 稀疏向量 */
#include <bits/stdc++.h>

#include <iostream>
using namespace std;
const int N = 1e8 + 10;
int arr[2][N];
int n, a, b;
int main() {
    int index, value;
    cin >> n >> a >> b;
    for (int i = 0; i < a; i++) {
        cin >> index >> value;
        arr[0][index]= value;
    }
    for (int i = 0; i < b; i++) {
        cin >> index >> value;
        arr[1][index] = value;
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        res =arr[0][i] * arr[1][i]+res;
    }
    cout << res;
    return 0;
}
/*
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40
 */

但是,这个解法只能够拿到60分为什么呢?你看题目要求,他的n的数据范围是到1e9的,但是我们并不能看那么大的数组,所以,对于题目后面四个测试样例,我们就过不了了。所以我们就必须想新的解决办法了。

双指针算法

废话

很巧,就在不久前,我也刚刚看了acwingyxc的基础算法课,也刚好看到了他讲的双指针算法,那时本来想写一点笔记的,但是发现那个东西并不好写,然后只能作罢了。在做这道题的时候,我也想到了双指针算法,但是我写的东西还是错的,至于为甚么,后面再讲,还有,我在写题目时还想到了用离散化来做,但自己也是没有写出来。算了,废话就不说了,下面开始讲解:

正文

我们可以这样子想:对于这两个向量uv,我们可以用一个结构体来存下它们的有用值的下标(index)以及它的值(value),然后找到这两个向量中下标相等的点,把他们的值相乘再相加就能够得到两个向量的内积了。思路是这样子的,应该也不难理解。然后下面讲讲双指针算法的优势是什么,讲完之后你们对双指针应该也会有一个了解了。

传统处理

按照我们一贯的思路,我们要找到两个向量中下标相等的值,那么我们可以把一个向量的某一个值暂时确定下来先,也就是作为第一重循环,然后在另一个向量中遍历寻找和该值对应的下标,这是第二重循环。然后我们来分析一下时间复杂度:

两个向量的维度最大可以达到5e5,那么时间复杂度就是$O(n^2)=(5e5)^2=25*e^{10}$,我们大概知道计算机1s能够处理的数据大概是1e8 我们题目要求的时间是2秒,也就是说,我们这么处理数据的话花费的时间是远远超过两秒的,那交上去必然会导致超时。那么这时候就能体现出双指针算法的优越之处了。

双指针算法

双指针算法怎么处理数据的呢?

我们分析传统处理方法,我们会发现对于每一个u向量中确定下来的值,我们都要把v中的每一个值无脑地拿出来进行比对。如果我对两个向量中的index从小到大排个序,如果当前u向量的下标(设为i)比v向量下标(设为j)大,那这时我应该要将j移到和i相等的位置才能做出比较,这样我就可以不用理会中间的那些值,也就是说,我的j值是跟这i的值走的。这样就可以让ij只遍历一遍数组就可以了,这样就能够把传统的$O(n^2)$的算法优化成$O(n)$的了。如果大家不能够理解我上面的描述的话那就琢磨一下代码吧。或这看一下我关于双指针算法的笔记。这里附上链接:{% post_link 算法基础/双指针算法 双指针算法 %}

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
pair<int, int> u[N], v[N];   //此处pair可以看成是一个结构体,里面有两个元素。但是它和自己定义的结构又有不同,具体百度
int n, a, b;
int main() {
	cin >> n >> a >> b;
	for (int i = 0; i < a; i++) {
		cin >> u[i].first >> u[i].second;
	}
	for (int i = 0; i < b; i++) {
		cin >> v[i].first >> v[i].second;
	}
	sort(u, u + a );
	sort(v, v + b );
	long long res = 0;
	for (int i = 0, j = 0; i < a && j < b; i++) {
		while (j < b && v[j].first < u[i].first)j++;
		if (j >= b)break;
		if (u[i].first == v[j].first)res += u[i].second * v[j].second;
	}
	cout << res;
	return 0;
}

代码2(双指针算法的另一种形式)

 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
/* 稀疏向量 */
using namespace std;
#include <bits/stdc++.h>
const int N = 5e5 + 10;
pair<int, int> u[N], v[N];
int n, a, b;
int main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= a; i++) {
        cin >> u[i].first >> u[i].second;
    }
    for (int i = 1; i <= b; i++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(u + 1, u + a + 1);
    sort(v + 1, v + b + 1);
    long long res = 0;
   
    int i = 1, j = 1;
    while (i <= a && j <= b) {
        if (u[i].first > v[j].first)
            j++;
        else if (u[i].first < v[j].first)
            i++;
        else {
            res += u[i].second * v[j].second;
            i++, j++;
        }
    }
    while (i <= a) {
        if (u[i].first == v[b].first) {
            res += u[i].second * v[b].second;
            break;
        }else i++;
    }
    while (j <= b) {
        if (u[a].first == v[j].first) {
            res += u[a].second * v[j].second;
            break;
        }
        else j++;
    }
    cout << res;
    return 0;
}

离散化的做法

声明:此处的代码不是本人写的,但是我找不到原作者的博客地址了,等找到再加上,如侵删。

 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
/* 稀疏向量 */
#include <iostream>
#include <map>
using namespace std;
map<int, int> mp;
int main() {
    int n, m1, m2;
    long long ans = 0;
    cin >> n >> m1 >> m2;
    for (int i = 0; i < m1; i++) {
        int num1, num2;
        cin >> num1 >> num2;
        mp[num1] = num2;
    }
    for (int i = 0; i < m2; i++) {
        int num1, num2;
        cin >> num1 >> num2;
        ans += mp[num1] * num2;
    }
    cout << ans;
}
/* 
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40

 */

小结

  1. 双指针算法可以优化传统的双重遍历
  2. 注意pair和自己定义的结构体的区别
  3. 学习使用一下map来实现离散化,这样不用自己写离散化函数

最后的话

这个题其实不算难吧(写出来后看),但是自己在写的过程中总是不能顺利地实现自己的想法,双指针和离散化我都有尝试过,但还是不能写出来,本来想把自己踩到的坑写一下的,但是没有时间了(写博客真的很费时间),等我以后休闲一点了在看着上来吧。其实我也已经把坑写到小结那里了,大家查查资料就能够学到了。好吧,那今天就到这里,拜拜啦!

0%