360笔试第二题AC解法

直接上代码，正好优化到 800ms 将将AC，如果代码有什么优化的可能，或者有了更好的思路欢迎评论

如果想看第一题的思路和第二题的思路，可以看我写的博客2020届360秋招笔试编程题。

由于是想要输出加和最大的数字,那么第一位的可能性就是从 M - 1 到 0,需要从中选出最大的那个.此时问题就会退化成一个 twosum ,从 M - 1 到 0 遍历,优先获得高的.

其实解题思路很简单,就是贪心,最最关键的是如何减少运算中的计算量.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int N, M; cin >> N >> M;
    unordered_map<int, int> nums1, nums2;
    vector<int> sum(M, 0);
    int tmp;
    for(int i = 0; i < N; ++i){
        cin >> tmp;
        ++nums1[tmp];
    }
    for(int i = 0; i < N; ++i){
        cin >> tmp;
        ++nums2[tmp];
    }
    int lr, mr;
    for(int i = M - 1; i >= 0; --i){
        auto nit1 = nums1.begin();
        while(nit1 != nums1.end()){
            lr = i - nit1->first;
            mr = M + i - nit1->first;
            if(nums2.find(lr) != nums2.end()){
                if(nums2[lr] <= nit1->second){
                    tmp = nums2[lr];
                    nums2.erase(lr);
                }else{
                    tmp = nit1->second;
                    nums2[lr] -= tmp;
                }
                nit1->second -= tmp;
                sum[i] += tmp;
            }
            if(nums2.find(mr) != nums2.end()){
                if(nums2[mr] <= nit1->second){
                    tmp = nums2[mr];
                    nums2.erase(mr);
                }else{
                    tmp = nit1->second;
                    nums2[mr] -= tmp;
                }
                nit1->second -= tmp;
                sum[i] += tmp;
            }
            if(nit1->second == 0){
                nums1.erase(nit1++);
            }else{
                ++nit1;
            }
        }
    }
    for(int i = M - 1; i >= 0; --i){
        for(int j = 0; j < sum[i]; ++j){
            cout << i << ' ';
        }
    }
    cout << endl;
    return 0;
}