网易2019校招笔试编程题参考代码

与更多牛友一起讨论笔试~

发本场网易笔试题解，赢取牛客T恤！

发题解，赢取卫衣~

代价

分析

升序排序相减即可。

时间复杂度

O(1)

参考代码

#include <bits/stdc++.h>

using namespace std;
int a[3];
int main() {
    int ans = 0;
    for(int i = 0; i < 3; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + 3);
    for(int i = 2; i > 0; i--) {
        ans = ans + a[i] - a[i - 1];
    }
    printf("%d\n", ans);
    return 0;
}

访友

分析

贪心，除了最后一步，每一次都走5步，若还有剩下，再走一步即可。

时间复杂度

O(1)

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long int n;
    cin >> n;
    cout << ceil((double)n / 5);
    return 0;
}

买房

分析

题目给定了房子数和已经入住的住户数量。
先考虑几个特例
n<=2，k<=1，n=k的情况下无法达成条件，故直接输出0 0
对于其它情况，显然最小的情况固定为0
对于k幢房子，在n足够大的情况下有k-1幢满足条件的房子(6 3时#-#-#-)，即(2*k-1)<=n时
否则为n-k，（6 4时#-#-##)

时间复杂度

O(1)

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k, t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        if(n <= 2 || k <= 1 || n == k) {
            printf("0 0\n");
            continue;
        }
        if((2 * k - 1) <= n) {
            printf("0 %d\n", k - 1);
        }
        else {
            printf("0 %d\n", n - k);
        }
    }
    return 0;
}

翻转翻转

分析

先考虑n = m = 1的情况，翻转一次，故输出1
我们令输入的n <= m
当n = 1,m > 1时，最边上两块会被翻转两次，中间的会被翻转三次，故输出（m - 2）
当2 <= n <= m时，四个角会被翻转四次，四边上除了角外的部分会被翻转六次，中间剩余的部分会被翻转九次，故输出(n - 2)(m - 2)

时间复杂度

O(1)

参考代码

#include <bits/stdc++.h>

using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        long long n, m;
        scanf("%lld%lld", &n, &m);
        if(n > m) swap(n, m);
        if(n == 1 && m == 1){
            printf("1\n");
            continue;
        }
        if(n == 1){
            printf("%lld\n", m - 2);
            continue;
        }
        printf("%lld\n", (n - 2) * (m - 2));
    }
    return 0;
}

橡皮泥斑马

分析

可以发现，无论操作多少次，总是由两段下标连续的串组成，所以直接在原串后面接上原串，求最长黑白相间连续串即可。

时间复杂度

O(|S|),其中|S|表示字符串长度

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    s += s;
    int ans = 1;
    for (int i = 0; i < s.size(); i++) {
        int j = 1;
        while (i != s.size() - 1 && s[i] != s[i + 1]) {
            i++;
            j++;
        }
        ans = max(ans, j);
    }
    if (s.size() / 2 < ans) {
        ans = s.size() / 2;
    }
    printf("%d\n", ans);
    return 0;
}

社团******

分析

暴力枚举这个人需要多少人支持才能当选，每次枚举时，超出这个数量以及和这个数量相等的人一定需要被改变，之后数量不足，再从剩下的人中选择。

时间复杂度

O(m n logn)

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3005;

vector<int> G[N];
int vis[N];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    ll ans = 1e18;
    for (int i = 0;i < n;i++) {
        int p, c;
        scanf("%d%d", &p, &c);
        G[p].push_back(c);
        vis[p]++;    
    }
    int mx = 0;
    for (int i = 1;i <= m;i++) {
        if (vis[i] > mx) {
            mx = vis[i];
        }
    }
    int cnt = 0;
    for (int i = 1;i <= m;i++) {
        if (vis[i] == mx) cnt++;
    }
    if (cnt == 1 && vis[1] == mx) return 0*puts("0");
    for (int i = 1; i <= m; i++) sort(G[i].begin(), G[i].end());
    for (int i = n; i >= 1; i--) {
        vector<int> r;
        int num = i - vis[1];
        ll sum = 0;
        for (int j = 1; j <= m; j++) {
            if (vis[j] >= i && j != 1) {
                int tmp = vis[j] - i + 1;
                for (int k = 0; k < min(tmp, (int)G[j].size()); k++) {
                    r.push_back(G[j][k]);
                } 
            }
        }
        for (int j = 0; j < r.size(); j++) {
            num--;
            sum += r[j];
        }
        if (num <= 0) {
            ans = min(ans, sum);
            continue;
        }
        r.clear();
        for (int j = 1; j <= m; j++) {
            if (vis[j] >= i && j != 1) {
                int tmp = vis[j] - i + 1;
                if (tmp >= G[j].size()) continue;
                for (int k = tmp; k < G[j].size(); k++) {
                    r.push_back(G[j][k]);
                } 
            }
        }
        for (int j = 1; j <= m; j++) {
            if (vis[j] < i && j != 1) {
                for (int k = 0; k < G[j].size(); k++) {
                    r.push_back(G[j][k]);
                }
            }
        }
        sort(r.begin(), r.end());
        for (int j = 0;j < r.size();j++) {
            num--;
            sum += r[j];
            if (num <= 0) break;
        }
        if (num <= 0) ans = min(ans,sum);
    }
    cout << ans << endl;
    return 0;
}

香槟塔

分析

每层塔建立一个mark标记指向离他最近的未装满的层，执行2操作时对当前层的mark进行添加，如果加满移至下一个mark。使用并查集路径压缩的思想不断把mark下移。执行1操作时直接输出结果。

时间复杂度

O(m + n)

参考代码

#include <bits/stdc++.h>

const int MAXN =  200015;

using namespace std;

int mark[MAXN], a[MAXN], b[MAXN];

int _find(int x) {
    if(x == 0) return x;
    if(a[x] != b[x]) return x;
    return mark[x] = mark[x + 1] = _find(mark[x + 1]);

}
int main() {
    int n, m, x, y, d;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = 0;
        mark[i] = i;
    }
    int op;
    while(m--) {
        scanf("%d", &op);
        if(op == 2) {
            scanf("%d%d", &x, &y);
            while(y) {
                x = _find(x);
                if(x == 0)break;
                d = min(a[x] - b[x], y);
                b[x] += d;
                y -= d;
            }
        }
        else {
            scanf("%d", &x);
            printf("%d\n", b[x]);
        }
    } 
    return 0;
}