20180324今日头条编程测试题：拼接数组 + Majicc操作

迷南。 2022-05-29 13:26 164阅读 0赞

![这里写图片描述][70]

师兄的做法很棒，这道题的思路是这样的，假如可以均分成i份，那么可以直接执行第二种操作i-1次，否者的话执行第一种操作。

#include <iostream>
    using namespace std;
    
    int main(){
        int n;
        cin>>n;
        int res=0;
        for(int i=2;i<=n;)
        {
           {
                res+=(i-1);
                n=n/i;
            }
            else
                ++i;
        }
        cout<<res<<endl;
        return 0;
    }

![这里写图片描述][70 1]

这一道题不太好想的地方时就是如何在添加和去除一个元素的同时还可以保证平均数变大，其实仔细想想还是很简单的，对于两个set，假设平均数分别是a和b，假如a

#include <iostream>
    #include <unordered_set>
    
    using namespace std;
    
    double avg(const unordered_set<int>& v) 
    {
        double sum = 0;
        for (int i : v) {
            sum  += i;
        }
        return sum/v.size();
    }
    
    int move(unordered_set<int>& a, unordered_set<int>& b) {
        double avg_a = avg(a), avg_b = avg(b);
        unordered_set<int> t;
        if (avg_a > avg_b) 
        return move(b, a);
    
        for (int i : b) {
        {
            if (avg_a < i && i < avg_b && a.find(i) == a.end())
             {
                t.insert(i);
            }
        }
    
        a.insert(t.begin(), t.end());
    
        for (int i : t) {
            b.erase(i);
        }
        return t.size();
    }
    
    int main() {
        int n, m, t;
        unordered_set<int> a, b;
        cin >> n >> m;
    
        for (int i = 0; i < n; ++i) {
            cin >> t;
    
            a.insert(t);
        }
    
        for (int i = 0; i < m; ++i) {
            cin >> t;
            b.insert(t);
        }
    
        int count = 0;
        while(true) {
            int r = move(a, b);
            if (r == 0) break;
            count += r;
        }
        cout << count << endl;
    }

[70]: /images/20220529/81093cfc51c34b45b3b5f7a2186bdc59.png
[70 1]: /images/20220529/98cdb0cfccd94b3d91b23bf810bb4fe1.png