MENU

枚举+优化(3)——哈希表优化实例1

June 6, 2018 • Read: 150 • 算法

例1

image

//两重循环枚举,时间复杂度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

image
为了描述方便,我们在水平方向建立一个X轴,X=0的位置设置成这面墙的左边缘。X轴的长度单位与砖的长度单位保持一致
image
比如第二层红色的缝隙坐标是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;
}
最后编辑于: March 21, 2019
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment