双指针Level1

偶然在codeforces上发现了这个教程，双指针一直是我掌握的不太好的地方（好的双指针可以用的出神入化），所以就学习一下。

课程网站：https://codeforces.com/edu/course/2/lesson/9。

---

下面是对应的练习题：https://codeforces.com/edu/course/2/lesson/9/1/practice。

A

题意

给你两个已经排好序的数组，将题目按照升序，合并成一个新数组并输出这个数组。

方法

采用双指针，一个从\(a\)数组的起点开始扫描，一个从\(b\)数组的起点开始扫描，逐个进行比较，较小的插入新数组中。

注意：

• 指针不能越界
• 可能会出现一个数组已经用完，另一个数组还存在一些元素的情况。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n,m;    cin>>n>>m;
    std::vector<ll> a(n,0),b(m,0);
    std::vector<ll> c;
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int i=0;i<m;i++)    cin>>b[i];
    int i=0,j=0;
    while(i<a.size() || j<b.size())
    {
        if(a[i]<b[j] && i<a.size() || j==b.size())
        {
            c.push_back(a[i]);
            i++;
        }
        else    c.push_back(b[j]),j++;
    }
    for(int i=0;i<c.size();i++)
    {
        cout<<c[i]<<" \n"[i==c.size()-1];
    }
}
int main()
{
    int t=1;
    //cin>>t;
    while(t--)  solve();
    return 0;
}

B

题意

给你两个已经排好序的数组，对\(b\)数组的每一个元素，找到\(a\)数组中小于该元素对应的个数。

方法

和上面基本一样，只需要在\(a_i>b_j\)时，记录答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n,m;    cin>>n>>m;
    std::vector<ll> a(n,0),b(m,0);
    std::vector<ll> c;
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int i=0;i<m;i++)    cin>>b[i];
    int i=0,j=0;
    std::vector<ll> ans;
    while(i<a.size() || j<b.size())
    {
        if(a[i]<b[j] && i<a.size() || j==b.size())
            i++;
        else ans.push_back(i),j++;
    }
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i]<<" \n"[i==ans.size()-1];
    }
}
int main()
{
    int t=1;
    //cin>>t;
    while(t--)  solve();
    return 0;
}

C

题意

给你两个已经排好序的数组，将找出这两个数组中，有多少个相同元素对。（即\(a_i==b_j\)）。

方法

在扫描到\(a_i==b_j\)时，我们可以先让\(i\)开始往后扫描，直到最后一个元素（满足\(a_i==b_j\)），\(j\)也是类似的处理，在这个过程中记录一下相同的个数，使用乘法原理得到答案。

其余的情况直接移动指针即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n,m;    cin>>n>>m;
    std::vector<ll> a(n,0),b(m,0);
    std::vector<ll> c;
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int i=0;i<m;i++)    cin>>b[i];
    int i=0,j=0;
    ll ans=0;
    while(i<a.size() || j<b.size())
    {
        if(a[i]==b[j])
        {
            int anum=1,bnum=1;
            i++;
            while(i<a.size() && a[i]==a[i-1])   i++,anum++;
            j++;
            while(j<b.size() && b[j]==b[j-1])   j++,bnum++;
            ans+=1ll*anum*bnum;
        }
        else if(a[i]<b[j] && i<a.size())    i++;
        else    j++;
    }
    cout<<ans<<"\n";
}
int main()
{
    int t=1;
    //cin>>t;
    while(t--)  solve();
    return 0;
}