京东秋招 2023.09.09 编程题目与题解

发表于 2023-09-10 更新于 2023-09-17 分类于笔试阅读次数：本文字数： 1.8k 阅读时长 ≈ 2 分钟

1、小红的差值

小红有一个长度为\(n\)的数组\(a\)。小红初始分数为\(0\)。

小红每次选择两个整数，这两个数的差值不能超过\(k\)，小红获得这两个数的乘积的分数，被选择过的数不能再选择。

问小红最多能获得多少分数?

输入

第一行输入两个整数\(n,k\)。

第二行输入\(n\)个整数\(a_i\)。

\(1\le n,k,a_i\le 10^5\)。

输出

输出一个整数。

样例

输入：
6 2
1 1 4 5 1 4

输出：
21

提示：
1和1配对，4和5配对。

解答

首先对数组\(a\)进行排序。假设目前已经满足\(a_1\le a_2\le \dots\le a_n\)。

根据贪心选择性质不难知道，对于已经选对的两对匹配\((i_1,j_1),(i_2,j_2)\)，可以证明要么\(j_1<i_2\)，要么\(j_2<i_1\)，即这两对匹配对应的区间不会相交。

因此，我们可以从大到小枚举这些数\(a_i(i\ge 2)\)，并判断\(a_i-a_{i-1}\le k\)是否成立，如果成立，那么这两个数匹配成一对；否则抛弃\(a_{i}\)，并寻找\(a_{i-2}\)（如果存在），并判断\(a_{i-1}\)和\(a_{i-2}\)即可。

最终，将每对匹配的乘积之和求出即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
int a[N],n,k;
int main(){
    ll ans=0;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=n;i>=2;){
        if(a[i]-a[i-1]<=k){
            ans+=1ll*a[i]*a[i-1];
            i-=2;
        }
        else --i;
    }
    printf("%lld\n",ans);
}

2、小红的地砖

小红有\(n\)块地砖，小红从第一块地砖开始，要走到第\(n\)块地砖，走到第\(i\)块地砖需要消耗\(a_i\)的体力值，小红每次可以选择向前走一步或者向前走两步，求小红走到第\(n\)块地砖时消耗的最小体力值。

输入

第一行输入一个整数\(n\)，表示地砖的数量。

第二行输入\(n\)个整数\(a_1,a_2,\dots,a_n\)，表示走到第\(i\)块地砖需要消耗的体力值。

\(1\le n\le 10^5\)
\(1\le a_i\le 10^3\)
\(a_1=a_n=0\)

输出

输出一个整数，表示小红走到第\(n\)块地砖时消耗的晨小休力值。

样例

输入：
5
0 3 2 1 0

输出：
2

提示：
依次走过[1, 3, 5]地砖。

解答

这道题是一道很简单的动态规划，每个状态最多只有两种不同的决策转移得到。因此，令\(f_i(1\le i\le n)\)表示走到第\(i\)块地砖时总共消耗的体力值，那么不难写出\(f\)的状态转移方程为：

\(f_i= \left \{\begin{aligned} &0 & & \text{if}\quad i=1 \\ &a_2 & & \text{if}\quad i=2 \\ &\min\{f_{i-2},f_{i-1}\}+a_i & & \text{if}\quad 3\le i\le n\\ \end{aligned}\right.\)

其中，方程的第三行表示要么从状态\(f_{i-2}\)走两块地砖而来，要么从\(f_{i-1}\)走一块地砖而来。

因此，最终答案为\(f_n\)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
int f[N],a[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    f[2]=a[2];
    for(int i=3;i<=n;i++)
        f[i]=min(f[i-1],f[i-2])+a[i];
    printf("%d\n",f[n]);
}

3、小红的数组

小红定义一个长度为\(m\)的数组\(b\)的权值为\(1\times b_1+2\times b_2+3\times b_3+...+m\times b_m\)。

现在小红有一个长度为\(n\)的数组\(a\)，她想知道所有子数组的权值和是多少？答案对\(10^9+7\)取模。

输入

第一行输入一个整数\(n\)。第二行输入\(n\)个整数\(a_i\)。

\(1\le n,a_i < 10^5\)

输出

输出一个非负整数，表示答案对\(10^9+7\)取模的结果。

样例

输入：
3
1 2 3

输出：
33

提示：
子数组[1]的权值是1。
子数组[1,2]的权值是5。
子数组[1,2,3]的权值是14。
子数组[2]的权值是2。
子数组[2,3]的权值是8。
子数组[3]的权值是3。

解答

对于某个数组元素\(a_i(i\in [1,n])\)，当一个子数组的左侧小于等于\(i\)，并且大于等于\(i\)时，那么这个元素便为这个子数组做出了贡献。

如果子数组的左侧为\(l(l\le i)\)，那么\(b_i\)将会做出\((i-l+1)\)倍的贡献。

同时，由于数组的右侧\(r(r\ge i)\)可以随意取，因此\(b_i\)每个倍率的贡献都有\(n-i+1\)次。

因此，这道题目的答案为

\(\begin{aligned} &\sum_{i=1}^n\sum_{l=1}^i (i-l+1)\cdot b_i\cdot (n-i+1)\\ =&\sum_{i=1}^n\sum_{l=1}^i l\cdot b_i\cdot (n-i+1)\\ =&\sum_{i=1}^n\dfrac{i(i+1)}{2}\cdot b_i\cdot (n-i+1)\\ \end{aligned}\)

最终直接计算最后一个求和式的结果即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll mod=1e9+7;
int main(){
    int n,x;
    scanf("%d",&n);
    ll ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        ans=(ans+1ll*i*(i+1)/2*(n-i+1)%mod*x)%mod;
    }
    printf("%lld\n",ans);
}