枚举+优化（3）——哈希表优化实例1

例1

//两重循环枚举，时间复杂度O(N^2)
#include <bits/stdc++.h>
using namespace std;
int n,k,a[100000];
set<pair<int,int>> myset;
int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    for(int i = 0;i < n;i++)
        for(int j = 0;j < n;j++)
            if(a[i] + k == a[j])
                myset.insert(make_pair(a[i],a[j]));
    cout<<myset.size()<<endl;
    return 0;
}

思考

优化，减少枚举变量，只枚举a[i]

如果我们只枚举a[i]，比如a[i] = 3，那么如果存在数对(a[i],a[j] + k)，假设我枚举数对里较小的值是3，那么根据差是2，较大的肯定就是5，所以，问题就变成查找a[i] + k在不在输入的数组里

//时间复杂度O(N)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,x,ans = 0;
    unordered_set<int> myset;
    cin >> n >> k;
    for(int i = 0;i < n;i++)
    {
        cin >> x;
        myset.insert(x);
    }
    for(int x:myset)
        if(myset.find(x+k) != myset.end())
            ans++;
    cout << ans << endl;
    return 0;
}

如果你的编译器不支持c++11，那你的程序可能要写的长一点

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,x,ans = 0;
    set<int> myset;
    cin >> n >> k;
    for(int i = 0;i < n;i++)
    {
        cin >> x;
        myset.insert(x);
    }
    set<int>:: iterator i = myset.begin();
    for(i;i != myset.end();i++)
        if(myset.find((*i) + k) != myset.end())
            ans++;
    cout << ans << endl;
    return 0;
}

例2.题目链接 hihocoder1494

为了描述方便，我们在水平方向建立一个X轴，X=0的位置设置成这面墙的左边缘。X轴的长度单位与砖的长度单位保持一致

比如第二层红色的缝隙坐标是8，第三层绿色缝隙坐标是11。现在假设我要在X=a这个位置画一条竖线，这条线穿过了多少块砖，显然取决于X=a这个位置有多少个缝隙。这个位置的缝隙越多，穿过砖块的数目就越少

思路

首先计算所有砖块交接缝隙的坐标，看哪个坐标的缝隙最多，我们就在哪个坐标画线，这样穿过的砖块肯定最少。我们可以用unordered_map来做，Key是缝隙的坐标，value是处于这个坐标的缝隙的数量。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,c,t,st;
    unordered_map<int,int> cnt;
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        cin >> c;
        st = 0;
        for(int j = 0;j < c;j++)
        {
            cin >> t;
            st += t;//每次放入砖块，坐标就要移动
            if(j != c - 1)//除了最后一行外，每行都要记录缝隙数
                cnt[st]++;//cnt[st]的值表示坐标的st的缝隙数量
        }
    }
    int mx = 0;
    for(auto it:cnt)//找最大的缝隙数
        if(it.second > mx)
            mx = it.second;
    cout<<n - mx<<endl;
    return 0;
}