枚举 + 优化（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;
}