9.4 网易后端笔试-题解

第一题 求两个数的最小差

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n;
int a[200005];

int main() {
    cin >> n;

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

    sort(a + 1, a + n + 1);

    int minSub = 0x3f3f3f3f;
    int ans1, ans2;
    for (int i = 2; i <= n; i++) {
        minSub = min(a[i] - a[i - 1], minSub);
    }

    cout << minSub << endl;

    return 0;
}

第二题 求乘积最大的数字拆分方式，枚举等分的份数即可

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n;

int gcdMath(int x, int y) {
    return x % y == 0 ? y : gcdMath(y, x % y);
}

int main() {
    cin >> n;

    if (n <= 4) {
        cout << n << ' ' << 1 << endl;
        return 0;
    }

    int i, last = 0;
    for (i = 2; i < n; i++) {
        double tmp = (double)n / i;
        double now = 1.0;
        for (int j = 1; j <= i; j++) {
            now *= tmp;
        }
        if (now < last) {
            i--;
            break;
        }
        else {
            last = now;
        }
    }

    int up = 1, down = 1;
    for (int k = 1; k <= i; k++) {
        up *= n;
    }
    for (int k = 1; k <= i; k++) {
        down *= i;
    }

    int gcd = gcdMath(up, down);
    up /= gcd;
    down /= gcd;

    cout << up << ' ' << down << endl;

    return 0;
}

第三题 求两个数组的差分数列数组的最长公共子数组，遍历一遍即可

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n;
int a[200005];
int b[200005];

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

    int ans = 0, idx = 1;
    while (idx < n) {
        int count = 0;
        while (idx < n && a[idx + 1] - a[idx] == b[idx + 1] - b[idx]) {
            count++;
            idx++;
        }
        ans = max(ans, count + 1);
        idx++;
    }

    cout << ans << endl;

    return 0;
}

第四题 可以确定的涂色块，二分搞一搞，看看方格一定会落到哪个颜色中

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

int a[1000005], sum[1000005];

int main() {
    int w, n, cur = 0;
    cin >> w >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        if (i != 1) {
            sum[i]++;
        }
    }
    vector<int> vc;
    for (int i = 1; i <= w; i++) {
        int pos = lower_bound(sum, sum + n + 1, i) - sum;
        pos--;
        int res = sum[n] - sum[pos];
        if (pos != 0) {
            res--;
        }
        if (w - i < res) {
            vc.push_back(i);
        }
    }
    cout << vc.size() << endl;
    for (int i = 0; i < vc.size(); i++) {
        if (i == vc.size() - 1) {
            cout << vc[i] << endl;
        }
        else {
            cout << vc[i] << " ";
        }
    }
    return 0;
}