四道编程题，好难。。。
第一题给出商品的价值和下架时间（第几天下架），每天只能买一样商品，下架以后不能买，问最多能获得的价值。dp表示当前天数能获得的最大价值，先按下架时间从小到大排序，先往背包里放早下架的，这样晚下架的肯定能接着放进背包。AC
for (int i = 1; i <= n; i++)
for (int j = goods[i].time; j > 0; j--)
dp[j] = max(dp[j], dp[j-1]+goods[i].val);
for (int j = 1; j <= max_day; j++)
ans = max(ans, dp[j]); 第二题给出两个数字P和Q，P至少走几步能变成Q，有四种走法：P = P-1; P = P - 2; P = P + 1; P = P * 2。P和Q比较大，这题直到最后五分钟才改出来，花了很长时间，思路就是用队列放置下一步可以达到的值，但是不优化会直接爆内存溢出，优化思路：如果该值已经使用过不需要再入队列（队列前面的数字操作次数肯定更小）因此加一个hashMap做已访问标记，如果当前值now比Q大，实际上只能使用前面两种走法了，假设当前已经走了x步，那么到达Q需要走的步数就是x+(now-Q+1)/2，用这个值来更新ans，注意到x其实是队列的层数（深度），具体代码写的特别复杂，大致思路如下。AC queue<long long> que;
que.push(P);
long long ans = 0x3f3f3f3f;
long long x = 0;
while (1) {
int n = que.size();
for (int i = 0; i < n; i++){
long long now = que.front();
que.pop();
if (now >= Q) {
ans = min(ans, x+(now-Q+1)/2);
continue;
}
que.push(now+1);
que.push(now*2);
que.push(now-1);
que.push(now-2);
}
if (ans <= x) {
break;
}
x++;
} 第三题给出N和M，求一个最小的可以被M整除的N位整数。（N指的是十进制数位数，N和M都很大） 先构造一个N位的整数X，也就是1后面N-1个0，然后 X / M * M，如果结果超过了N位限制返回-1，由于N和M都很大我估计得写大整数除法乘法，遂放弃，小数据过了20%。
第四题题目特别长，有N个座位，每天会有一个新员工i入座到Pi位置，产生Li幸福度，假设任意一个员工j所在位置的区间[j-d,j+d]内所有员工幸福度之和超过了x则该员工特别幸运，这一天作为幸运日输出。感觉可能是用树状数组模拟吧，但是题目又臭又长，写不动，0%。
听朋友说pdd不喜欢校招，这个笔试有点劝退啊。。。
全部评论
(1) 回帖