京东秋招 2023.09.02 机试题目与题解

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

1、讨厌鬼的区间

讨厌鬼和小甜妹相互暗恋很久了，今天他们终于有机会了。

讨厌鬼有三个区间\([l_1,r_1],[l_2,r_2],[l_3,r_3]\)，讨厌鬼和小甜妹在这三个区间中同时选择一个自己喜欢的区间，这两个区间不能相同。

接下来讨厌鬼和小甜妹需要在自己喜欢的区间内选择一个数，为了讨对方欢心，他们选择的数也必须同时在对方的区间内，并且这两个数的和需要尽可能大。

请你帮助讨厌鬼和小甜妹找到这两个数的和最大是多少。

输入

第一行输入\(6\)个整数表示\(l_1,r_1,l_2,r_2,l_3,r_3(1\le l_1,r_1,l_2,r_2,l_3,r_3\le 10^9)\)。

输出

输出一个整数，表示两个数和的最大值，若不存在这样的值，则输出\(-1\)。

样例

输入：
1 3 2 4 4 6

输出：
8

提示：
讨厌鬼选区间[2,4]，小甜妹选区间[4,6]。讨厌鬼和小甜妹均选择4。

解答

不失一般性，假设两人选择的区间分别是\([l_0,r_0],[l_1,r_1]\)。

由于选择的数既要在自己的区间，又要在对方的区间，因此令\(l=\max\{l_0,l_1\},r=\min\{r_0,r_1\}\)。这两个人选择的数必定在\([l,r]\)中，如果\(l>r\)，那么这是一个空区间，无法选择，否则只需要选择最大的数\(r\)即可。

代码

a = list(map(int, input().split()))
seg = [(a[0], a[1]), (a[2], a[3]), (a[4], a[5])]


def solve(s1, s2):
    s = (max(s1[0], s2[0]), min(s1[1], s2[1]))
    return -1 if s[0] > s[1] else s[1]


ans = -1
for i in range(len(seg)):
    for j in range(i):
        k = solve(seg[i], seg[j])
        if k >= 0:
            ans = max(ans, k * 2)
print(ans)

2、小红购物

小红准备买\(n\)件物品，第\(i\)件物品的价格是\(a_i\)。另外，小红有\(m\)种优惠券，第\(i\)个优惠券是：买一件价格不小于\(b_i\)的商品时，可以减去\(c_i\)的价格。每件商品最多只能用一次优惠券。每种优惠券可以用多次。小红想知道，自己买全部商品最少需要花多少钱？

输入

第一行输入两个正整数\(n,m\)，代表商品数量和优惠券的种类数。

第二行输入\(n\)个正整数\(a_i\)，代表每件商品的价格。

接下来的\(m\)行，每行输入两个正整数\(b_i,c_i\)，代表第\(i\)种优惠券的信息。

\(1\le n,m\le 200000\)
\(1\le a_i\le 10^9\)
\(1\le c_i<b_i\le 10^9\)

输出

一个正整数，代表最终需要花的最少钱数。

样例

输入：
3 2
4 8 6
5 1
8 5

输出：
12

提示：
第二件商品选择第二种优惠券，价格减到了3元；第三件商品选择第一种优惠券，价格减到了5元。总花费：4+3+5=12

解答

可见，对于第\(i\)件商品，这里选用的优惠券的下界\(b_i\)只需要比\(a_i\)低即可。

那么，我们首先对优惠券\((b_i,c_i)\)按照\(b_i\)进行升序排序。那么对于第\(i\)个商品，我们只需要找到最大的\(j(j\le n)\)满足\(b_j\le a_i\)。令此时的\(j\)为\(p_i\)，那么商品\(i\)实际的支付价格为\(\displaystyle{a_i-\max_{j=1}^{p_i}\{c_j\}}\)，也就是说在能够选择的优惠券中选择最优的。

但是如果直接暴力枚举每个\(p_i\)仍然是会超时的。可以发现，如果\(a_i\)越大，那么\(p_i\)也就越大。因此我们可以也对\(a\)进行排序，再使用双指针法求出\(\displaystyle{a_i-\max_{j=1}^{p_i}\{c_j\}}\)的值。

最终只需要将这些价格相加即可。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
# define X first
# define Y second
using namespace std;
typedef long long ll;

const int N=200004;
pi pa[N];
int a[N];
int n,m;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%d %d",&pa[i].X,&pa[i].Y);
    }
    sort(a+1,a+n+1);
    sort(pa+1,pa+m+1);
    ll ans=0;
    int mx=0;
    for(int i=1,j=1;i<=n;i++){
        for(;j<=m&&pa[j].X<=a[i];j++){
            mx=max(mx,pa[j].Y);
        }
        ans+=a[i]-mx;
    }
    printf("%lld\n",ans);
}

3、小红的蛋糕切割

小红拿到了一个矩形的蛋糕，共分成了\(n\)行\(m\)列，共\(n\ast m\)个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。

小红希望切割出一个正方形的小蛋糕（正方形边长必须平行于矩阵的边长，且必须都是完整的区域），自己吃掉正方形的部分，把剩下的部分给小紫吃。

小红希望两人吃的部分的美味度之和尽可能接近，小红吃的蛋糕美味度之和为\(s_1\)，小紫吃的蛋糕美味度之和为\(s_2\)，请你输出\(|s_1-s_2|\)的最小值。

输入

第一行输出两个正整数\(n\)和\(m\)，代表蛋糕区域的行数和列数。

接下来的\(n\)行，每行输入\(m\)个正整数\(a_{ij}\)，用来表示每个区域的美味度。

\(1\leq n,m \leq 10^3\)
\(1\leq a_{ij} \leq 10^4\)

输出

一个整数，代表\(|s_1-s_2|\)的最小值。

样例

输入：
3 3
1 2 3
2 3 4
3 2 1

输出：
1

提示：
如下方框内为小红食用的部分
 1 2 3
+-+-+
|2 3|4
|   |
|3 2|1
+-+-+

解答

通过二维前缀和：\(\displaystyle{s_{xy}=\sum_{i=1}^x\sum_{j=1}^y a_{ij}}\)，其中\(s_{0,\cdot}=s_{\cdot,0}=0\)，我们可以轻松地在\(O(1)\)时间内求出一个子矩阵的和，对于\(i\in [1,n],j\in [1,m]\)，\(s_c[x,y]\)可以通过下列递推式进行求出：

\[s_{xy}=s_{x-1,y}+s_{x,y-1}-s_{x-1,y-1}+a_{xy}\]

对于左上角为第\(x_1\)行第\(y_1\)列，右下角为第\(x_2\)行第\(y_2\)列的子矩阵，下面式子可以正确地计算出这个子矩阵中所有元素的和：

\[s(x_1,y_1,x_2,y_2)=s_{x_2,y_2}-s_{x_1-1,y_2}-s_{x_2,y_1-1}+s_{x_1-1,y_1-1}\]

回到本题。可见，由于这样的正方形蛋糕有\(O(n^3)\)个，因此直接枚举每个正方形蛋糕是超时的。可以发现，每个蛋糕的美味度都是正数，这意味着包含的蛋糕越多，美味度越大。因此，我们可以枚举每个点作为右下角，并且对正方形的边长进行二分即可。更具体的说，令\(f(x,y,l)=s(x,y,x-l+1,y-l+1)\)，枚举每个\((x,y)\)，通过二分找到\(l:0\le l\le \min\{i,j\}\)来找到满足\(2f(x,y,l)\le s_{nm}\)的最大\(l\)，那么此时其中一个答案为\(|s_{nm}-f(x,y,l)|\)。由于小红也可以比小紫吃得多，因此如果\(l<\min\{i,j\}\)，那么\(|s_{nm}-f(x,y,l+1)|\)也是一个候选答案。

代码

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

const int N=1004;
ll s[N][N];
int n,m;
ll cal(int x,int y,int l){
    return s[x][y]-s[x-l][y]-s[x][y-l]+s[x-l][y-l];
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%lld",&s[i][j]);
            s[i][j]+=s[i][j-1]+s[i][j-1]-s[i-1][j-1];
        }
    }
    ll ans=s[n][m];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int k=min(i,j);
            int l=0,r=k;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(cal(i,j,mid)*2<=s[n][m]) l=mid;
                else r=mid-1;
            }
            ans=min(ans,abs(s[n][m]-cal(i,j,l)*2));
            if(l<k){
                ans=min(ans,abs(s[n][m]-cal(i,j,l+1)*2));
            }
        }
    }
    printf("%lld\n",ans);
}