专栏首页mathor枚举+优化(3)——哈希表优化实例

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

例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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2017百度之星资格赛

     题目大意是说,给你n个熊(那么他们编号默认就是1...n),然后给定m行输入,每一行都有u,v,w三个变量,表示u熊和v熊之间有强关系w,然后问你至少需...

    mathor
  • 2017百度之星初赛(A)

     假设P进制下有个数(abc)~P~,若这个数满足:(abc)~P~ % B == 0,则以下两个等式一定成立:

    mathor
  • 2018年全国多校算法寒假训练营练习比赛(第二场)

     背包问题,只是特殊处理一下h为0和不为0的情况就行  若h=0,卡不了bug,就是正常的o-1背包  若h不等于0,可以卡bug,假设第i件武器是卡b...

    mathor
  • 2017百度之星资格赛

     题目大意是说,给你n个熊(那么他们编号默认就是1...n),然后给定m行输入,每一行都有u,v,w三个变量,表示u熊和v熊之间有强关系w,然后问你至少需...

    mathor
  • poj 2681 字符串

    瑾诺学长
  • HDU-5912-Fraction

    ACM模版 描述 ? 题解 简单的模拟问题,一个循环搞定。 代码 #include <iostream> using namespace std; cons...

    f_zyj
  • POJ3723 《挑战程序设计竞赛》踩坑

    我看书上的代码,觉得这一行有错误, //这里为什么要加上女生的人数而不是男生的人数?我认为应该加男生的人数 es[j].v = v+N; 所以我就没这样写,我...

    kalifa_lau
  • 一笔画问题

    l样例输入:第一行n,m,有n个点,m条边,以下m行描述每条边连接的两点。 l    5 5 l    1 2 l    2 3 l    3 4 l    4...

    attack
  • 【CodeForces 625C】K-special Tables

    第k列前的格子1 2 .. 按要求填到满格,然后第k列及后面的格子,都从左到右填递增1的数。

    饶文津
  • POJ - 2195 Going Home 最小费用最大流

    题意:多组输入,n行m列矩阵包含相等个数的 ‘m’ 和 ‘ H ’ 每个men要到达Home,每移动一个格子耗费 1,求最小花费。

    用户2965768

扫码关注云+社区

领取腾讯云代金券