网易C++后台开发笔试编程题

通过： 100 0 100 100

第一题，水题，直接在牛客上写的，没保存代码

第二题，一眼题，实在不知道自己哪里写错了，用了各种方法都不行。思路：只要堆高度为 0 1 2 3 4 5 ....就行

第三题，尺取法，前缀法维护下

typedef long long LL;

using namespace std;

int T;
int n;
int a[MAXN];
LL sum[MAXN];
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        memset(sum, 0, sizeof(sum));
        scanf("%d", &n);

        for(int i=1; i<=n; i++)
        {
            scanf("%d", a+i);
            sum[i] = sum[i-1]+a[i];
        }

        if(n == 1)
        {
            puts("1");
            continue;
        }

        int ans = 1;
        int cur = 1;
        for(int i=1; i<=n; i++)
        {
            while(cur <= n && a[cur] >= sum[cur-1] - sum[i-1])
            {
                ans = max(ans, cur-i+1);
                cur++;
            }
            if(cur > n)
                break;

        }
        printf("%d\n", ans);
    }
    return 0;
}

第四题， dp

dp[i][j] 表示前 i 个数生成 j 的最小代价

$dp[i+1][j] = min\{ dp[i][k] + abs(a[i+1] - \frac{j}{k})\} , k|j$

typedef long long LL;
using namespace std;
int n, b;
int a[1007];
int dp[1007][1007];
vector<int> fac;
map<int, int> mp;
int main()
{
    scanf("%d%d", &n, &b);
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
    for(int i=1; i*i<=b; i++)
    {
        if(b%i == 0)
        {
            if(i != b/i)
            {
                fac.push_back(i);
                fac.push_back(b/i);
            }
            else
                fac.push_back(i);
        }
    }
    sort(fac.begin(), fac.end());
    int tot = fac.size();

    for(int i=0; i<tot; i++)
        dp[1][i] = abs(fac[i] - a[0]);

    for(int i=2; i<=n; i++)
    {
        for(int j=0; j<tot; j++)
        {
            dp[i][j] = 0x7fffffff;
            for(int k=0; k<=j; k++)
            {
                if(fac[j] % fac[k] == 0)
                {
                    dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(a[i-1] - fac[j]/fac[k] ));
                }
            }
        }
    }
    printf("%d\n", dp[n][tot-1]);
    return 0;
}

#网易##笔试题目##C/C++#