网易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 的最小代价
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;
}
