百度秋招 2023.09.12 编程题目与题解（算法岗）

发表于 2023-09-13 分类于笔试阅读次数：本文字数： 1.2k 阅读时长 ≈ 1 分钟

1、队列

给定一个长度为\(n\)的序列\(a_1,a_2,\dots,a_n\)，你可以选择删去其中最多\(n-1\)个数，得到一个新序列\(b_1,b_2,\dots,b_m(1\le m\le n)\)。（只是删去后的序列，不改变原来的相对顺序）

现在你希望删去某些数使得新序列的第\(i\)个数的值恰好为\(i\)，即\(b_i=i\)。

现在你想知道最少需要删去多少个数使得新序列满足条件。

如果无论如何都不能做到，请输出\(-1\)。

输入

第一行一个正整数\(n\)，表示序列长度。

接下来一行\(n\)个空格隔开的数字\(a_1,a_2,\dots,a_n\)。

输出

输出一个整数表示最少需要删去的个数，如果做不到，输出\(-1\)。

样例

输入：
5
1 4 2 3 5

输出：
2

提示：
删去第二个数字4和第五个数字5，剩下1,2,3即可满足条件。

输入：
3
3 3 2

输出：
-1

提示：
无论如何都做不到，输出-1。

输入：
5
1 2 3 4 5

输出：
0

提示：
不需要删除就可以得到序列b。

解答

为了保证产生的\(b\)序列足够长，我们先寻找\(a\)中的第一次出现的\(1\)，将它记录下来\(b\)中，并将其余已经遍历的元素删除；接下来继续向后寻找到第一次出现的\(2\)，再将它记录下来，由此一直循环，直到下一个数无法在\(a\)中寻找到，这时打印被删除的数的个数即可。

如果所有数都被找遍了，却连\(1\)都没找到，那么输出\(-1\)。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,x,k=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(x==k) ++k;
    }
    printf("%d\n",k==1?-1:n-(k-1));
}

2、组队

小明的公司要进行集体活动，活动要求所有人员分组。

当前有\(n\)个人，每个人的能力值为\(a_i\)，性格值为\(b_i\)，现在希望将这\(n\)个人分成若干组，每个人只能在一个组内。

当然，分组是一个问题，我们定义两个人的差别值为能力值的差和性格值的差的和，即\(|a_i-a_j|+|b_i-b_j|\)。

在分组前，我们规定一个差别上限\(L\)，如果两个人的差别值不超过\(L\)，那么在分组结果中这两人一定会在同一组内（当然，即使两个人差别值超过\(L\)，两个人还是可以在同一个小组，只是不超过\(L\)的必须在一组）。

现在我们想知道，如果能将所有人分成至少\(k\)个非空的小组，规定的差别上限最多为多少。

输入

第一行两个正整数\(n,k\)，表示人数和分组要求。

接下来两行每行\(n\)个整数，表示\(a_1,a_2,\dots,a_n\)和\(b_1,b_2,\dots,b_n\)。

数据范围和说明

\(2\le k\le n\le 500,1\le a_i,b_i\le 10^5\)
保证任意两个人的能力值或者性格值至少有一项不同。

注：由于\(k>1\)，所以答案一定不为无穷大。

输出

输出一个整数表示最大的差别上限。

样例

输入：
3 2
1 9 3
2 7 8

输出：
7

提示：
1和2的差别值为9-1+7-2=13
2和3的差别值为9-3+8-7=7，
1和3的差别值为3-1+8-2=8，故差别上限为7时，2和3必须在一组，1单独一组，此时有2组。
而上限为8时，2和3必须在一组，1和3必须在一组，所以1,2,3只能一起一组，此时只有一组，不满足要求。
故上限最多为7。

解答

假设这些人两两之间的关系是一个图，如果两个人\(i,j\)的差别值不超过\(L\)，那么就在\(i,j\)之间连一条边。因此分组数就相当于图中的连通块数量。

为了方便，我们可以使用并查集来求解连通块数量（当然也可以使用bfs，但是并查集更简洁）。

随着差别上限\(L\)的增长，越来越多的边被加入图中，图中的连通块数量也在减少。因此，我们可以通过对差别上限\(L\)进行二分，使得找到最大的一个\(L\)，满足这时的图至少有\(k\)个连通块。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=504;
int a[N],b[N],n,k;
int fa[N];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int cal(int x){
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(abs(a[i]-a[j])+abs(b[i]-b[j])<=x)
                merge(i,j);
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(find(i)==i) ++cnt;
    return cnt;
}
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    int l=0,r=3e5;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(cal(mid)>=k) l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
}