首页 > 技术交流 > 网易C++后台开发笔试编程题

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

头像
MoonChasing
编辑于 2019-09-21 17:35:33 APP内打开
赞 3 | 收藏 3 | 回复1 | 浏览520
通过: 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 的最小代价

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;
}


1条回帖

回帖
加载中...
回帖

相关热帖

技术交流近期热帖

近期精华帖

热门推荐