简单算法的小应用

简单算法的小应用

最近在牛客网上经常进行一些算法的练习，分享两个好玩的题目。

附上牛客网的链接，当然了，和ACM大神相比，这些题是入门的，想学习的童鞋就温故知新一下吧。对了这是一个比较好的平台，大家可以没事来练练手。

排序问题

不知道为啥这个题目被分在了排序算法中，我在写这道题目的时候，为了提高效率，使用了二分查找，快排等算法，依然运行超时了，真的是很难过。后来我删除了复杂的排序，直接暴力求解，反而可以了。

传送门如下：牛客网

题解如下：

我这里是使用map结构来存储主要数据的，当然效率最高内存最小的就是使用数组了；但是我为了方便理解就没有使用数组。按照基数排序的思想，我把电影的语言存在对应下标的数组中了，这样的查找效率是最高的，因为你不管怎么排序，每次去遍历是很费时的。还有一个小要点就是，你对数组下标的频繁访问（哪怕是同一个下标），不如用临时变量存储的效率高。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

struct Movie{
    int bj;
    int cj;
    int scoreb;
    int scorec;
    int index;
};
int main()
{
    int n,m,firstScore=0,secondScore=0,index=1;
    cin >> n;
    map<int,int> strMap;
    for(int i = 0; i < n;i++){
        int temp;
        cin >> temp;
        strMap[temp]++;
    }
    cin >> m;
    Movie ret[m];
    for(int i = 0; i < m;i++){
        //这样真的很耗时间
        ret[i].cj = 0;
        ret[i].bj = 0;
        ret[i].scoreb = 0;
        ret[i].scorec = 0;
        ret[i].index = i+1;
        cin >> ret[i].bj;
    }
    //sort(a, a+n);
    for(int i = 0; i < m;i++){
        cin >> ret[i].cj;
        //这里如果不使用temp变量，用下标访问，时间开销会多很多
        //ret[i].scoreb = caculateNum(ret[i].bj,a,n);
        //ret[i].scorec = caculateNum(ret[i].cj,a,n);
        int tempb = strMap[ret[i].bj];
        int tempc = strMap[ret[i].cj];
        int tempi = ret[i].index;
        if(tempb >= firstScore){
            if(tempb > firstScore){
                firstScore = tempb;
                secondScore = tempc;
                index = tempi;
            }else{
                if(tempc > secondScore){
                    secondScore = tempc;
                    index = tempi;
                }
            }

        }
    }
//    sort(ret, ret+m, CmpByValue());
    cout<<index<<endl;
    return 0;
}

排序问题2

这个题目就比较简单了，就是一个排序之后，求最优的过程。

传送门如下：牛客网

题解如下：

直观的想，假设我们将货仓建在第k个商店的坐标上，那么货仓左边有 k - 1 个商店，右边有 n - k - 1 个商店，当我们将货仓向右移动一个单位，那么货仓距离左面所有的商店的距离就会增加一个单位，距离右面所有的商店的距离会减少一个单位，所以应当使左右商店的个数相同， k-1 = n-k-1, 那么k=n/2, k就是整个序列中位数的位置。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    int spc = a[n >> 1];
    int res = 0;

    for (int i = 0; i < n; i++)
        res += abs(a[i] - spc);

    cout << res << endl;
}