首页 > 网易互娱0812笔试,暴力暴力暴力
头像
offer快到碗里来1005
发布于 2020-08-12 22:14
+ 关注

网易互娱0812笔试,暴力暴力暴力

第一题,暴力
#include <iostream>
#include <vector>

using namespace std;

bool helper(const vector<int> &a,
            const vector<int> &b,
            const vector<int> &c)
{
    int W[10] = {0};
    W[1] = W[4] = W[7] = 1;
    int B[10] = {0};
    B[2] = B[5] = B[8] = 1;
    int T[10] = {0};
    T[3] = T[6] = T[9] = 1;

    int cnt = 0;
    for (auto i : a){
        if (W[i] == 1){
            --W[i];
            ++cnt;
        }
    }
    for (auto i : b){
        if (B[i] == 1){
            --B[i];
            ++cnt;
        }
    }
    for (auto i : c){
        if (T[i] == 1){
            --T[i];
            ++cnt;
        }
    }
    return cnt >= 7;
}

int main()
{
    int len;
    cin >> len;
    while (len--){
        vector<int> W, B, T;
        for (int i = 0; i < 7; ++i){
            string s;
            cin >> s;
            if (s.size() != 2)
                continue;
            if (s.back() == 'W'){
                W.push_back(s[0] - '0');
            }
            else if (s.back() == 'B'){
                B.push_back(s[0] - '0');
            }
            else if (s.back() == 'T'){
                T.push_back(s[0] - '0');
            }
        }

        if (helper(W, B, T) || helper(W, T, B) 
            || helper(T, W, B) || helper(T, B, W) 
            || helper(B, W, T) || helper(B, T, W)){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }
}
第二题,暴力
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> helper(vector<vector<int>>& nums){
    if(nums.empty()) return nums;

    int len = nums.size();
    vector<int> row(len);
    vector<int> col(len);
    for(int i=0; i<len; ++i){
        for(int j=0; j<len; ++j){
            row[i] += nums[i][j];
        }
    }
    for(int i=0; i<len; ++i){
        for(int j=0; j<len; ++j){
            col[i] += nums[j][i];
        }
    }

    int mx = 0, r = 0, c = 0;
    for(int i=0; i<len; ++i){
        for(int j=0; j<len; ++j){
            if(row[i] + col[j] - nums[i][j] > mx){ 
                mx = row[i] + col[j] - nums[i][j];
                r = i;
                c = j;
            }
        }
    }
    cout<< r+1 << " " << c+1 <<endl;

    vector<vector<int>> newNums;
    for(int i=0; i<len; ++i){
        if(i == r) continue;
        vector<int> line;
        for(int j=0; j<len; ++j){
             if(j == c) continue;
             line.push_back(nums[i][j]);
        }
        newNums.emplace_back(line);
    }
    // helper(newNums); //递归只能过30%,消耗过多的栈空间
    return newNums;        
}

int main(){
    int len;
    cin >> len;
    vector<vector<int>> nums(len);
    for(int i=0; i<len; ++i){
        vector<int> line(len);
        for(int j=0; j<len; ++j){
            int n; cin >> n;
            line[j] = n;;
        }
        nums[i] = std::move(line);
    }
    while(!(nums = helper(nums)).empty()) ; // 迭代不消耗额外栈空间, 100%
}

第三题, 真不是暴力...
#include <iostream>
#include <unordered_map>
#include <stack>
#include <climits>

using namespace std;

int main()
{
    int total; cin >> total;
    while(total--){
        unordered_map<int, int> mp; // event_id,  begin_time
        stack<pair<int, int>> stk;  // begin_time, cost_time
        int id = INT_MAX;
        int mx = 0;

        int item; cin >>item;
        while(item--){
            int t, e, s;
            cin >> t >> e >> s;
            if(s == 0){
                mp.insert({e, t});
            }else if(s == 1){
                int curTotalTime = t - mp[e];
                int curSelfTime = curTotalTime;
                while(!stk.empty() && stk.top().first > mp[e]){
                    curSelfTime -= stk.top().second;
                    stk.pop();
                }
                stk.push({mp[e], curTotalTime});
                if(curSelfTime > mx){
                    mx = curSelfTime;
                    id = e;
                }else if(curSelfTime == mx && e <id){
                    id = e;
                }
            }
        }
        cout<< id <<endl;
    }
}



没了。

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

近期精华帖

热门推荐