阿里云智能 秋招 2023.09.17 编程题目与题解（算法岗）

发表于 分类于 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

1、小红的字符串

某个国家有\(n\)个城市，第个城市的人口为\(a_i\)人。如果某个城市的人口不超过其他任何一个城市人口的两倍，那么这是一个稳定的城市。国家可以对城市执行政策，从而改变城市人口的数量，最少需要对几个城市执行政策，才能使得所有的城市都变得稳定。

输入

第一行一个整数\(n\)，表示城市的数量。

接下来一行\(n\)个整数，第\(i\)个整数表示第个城市的人口\(a_i\)。

  • \(1\le n\le 10^5\)
  • \(1\le a_i\le 10^9\)

输出

输出一个整数，表示最少需要修改的城市数量。

样例

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

输出：
1

解答

这题是简单的贪心。将数组\(a\)排好序后，对于每个\(l\in[1,n]\)，我们找到最大的\(r\in[1,n]\)，使得\(a_r\le 2\cdot a_l\)，这说明间\([l,r]\)内的城市都不需要整改，其余的\(n-(r-l+1)\)个城市都需要，因此使用双指针法求得每个\(r\)，最终取n-(r-l+1)的最小值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# include <bits/stdc++.h>

using namespace std;
const int N=100004;

int a[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int ans=n;
    for(int l=1,r=1;l<=n;l++){
        for(;r<=n&&a[r]<=a[l]*2;r++);
        ans=min(ans,(l-1)+(n+1-r));
    }
    printf("%d\n",ans);
}

2、小红选点

坐标轴上有\(n\)个点，小红希望选出其中\(m\)个点，并且这\(m\)个点两两之间距离都不超过\(k\)，求有多少种选点方案。

输入

一行三个整数 \(n,m,k\)，表示点的个数，选点的个数，以及两两之间距离不超过\(k\)。

接下来一行\(n\)个整数\(x_i\)，表示每个点的坐标。

  • \(2\le m\le 4\)
  • \(m\le n\le 10^5\)
  • \(1\le x_i,k\le 10^9\)

输出

输出一个整数，表示方案数，由于答案可能很大，输出答案对\(10^9+7\)取模的结果。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入：
4 2 3
1 2 3 4

输出：
6

提示：
任选两个点都可以满足条件。

输入：
4 2 2
1 2 3 4

输出：
5

提示：
可以选(1,2),(1,3),(2,3),(2,4),(3,4)这5种方案。

解答

首先对这些点的坐标进行排序，假设已经满足了\(x_1\le x_2\le \dots\le x_n\)。

为了不重不漏地计算出所有方案数，对于每个点\(x_l(l\in[1,n])\)，我们固定选择这个端点，然后其余端点只能在\(l\)的右侧选择。对于每一个\(l\)，我们可以使用双指针法找到一个最大的\(r\in[l,r]\)，满足\(x_r-x_l\le k\)，（这意味着\(r\)右侧的所有顶点都不能选）。这时，\([l,r]\)内的项点都可以任意选择。由于\(x_l\)已经被固定选择了，因此按照组合数的思想，我们有\(\dbinom{(r-l+1)-1}{m-1}=\dbinom{r-l}{m-1}\)种方法选择这些点，将这个值计到答案即可。

为了多次计算\(\dbinom{k}{m-1}\)，其中\(k\in[0,n]\)的所有值，我们可以通过只打印杨辉三角的第\(0\sim m-1\)列完成（注意这里的m非常小）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=100004,M=5;
ll mod=1e9+7;
ll C[N][M];
int x[N],n,m,k;
int main(){
    scanf("%d %d %d",&n,&m,&k);
    for(int i=0;i<=n;i++){
        C[i][0]=1;
        if(i<M) C[i][i]=1;
        for(int j=1;j<i&&j<M;j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    sort(x+1,x+n+1);
    for(int l=1,r=1;l<=n;l++){
        for(;r<=n&&x[r]-x[l]<=k;r++);
        ans=(ans+C[r-l-1][m-1])%mod;
    }
    printf("%lld\n",ans);
}

3、合并区间

现有\(n\)个区间\([l,r]\)。最多进行两次操作，每次操作选择两个相交的区间\([u,v]\)和\([x,y]\),增加一个新的区间\([\min(u,x),\max(v,y)]\)。

问，最多进行两次操作后，可以获得最长的区间的长度是多少？

假设两个区间分别是\([l_1,r_1]\)和\([l_2,r_2]\)，如果它们满足\(l_1\le l_2\le r_1\)或\(l_2\le r_1\le r_2\)，则认为这两个区间相交。假设一个区间是\([l,r]\)，认为这个区间的长度为\(r-l\)。

输入

第一行一个整数\(n\)。

接下来\(n\)行每行两个整数\(l_i,r_i\)。

  • \(1\le n\le 10^5\)
  • \(1\le l_i\le r_i\le 10^9\)

输出

输出一个整数。

样例

1
2
3
4
5
6
7
8
9
10
输入：
5
1 3
2 6
4 8
5 7
9 10

输出：
7

解答

依照贪心的思想，如果区间\([l_1,r_1]\)包含了另外一个区间\([l_2,r_2]\)，即\(l_1\le l_2\le r_2\le r_1\)，那么选择区间\([l_2,r_2]\)是完全没有必要的。因此我们可以删去这种区间。

这类被包含的区间可以使用以下方法进行删除：首先对所有区间进行排序，第一关键字为左端点，升序，第二关键字为右端点，降序。按照这个顺序遍历所有区间，如果当前区间的右端点并不能严格超过上一个被加入的区间，那么这个区间是被包含的，需要被清除，否则加入这个区间。

最终我们处理出来了\(m\)个区间\([l_1',r_1'],[l_2',r_2'],\dots,[l_1',r_1']\)，它们必定满足\(l_1'<l_2'<\dots<l_m',r_1'<r_2'<\dots<r_m'\)。

那么我们选择的\(3\)个相交区间应该距离尽可能拉长，令状态\(f(i,j)(1\le i\le 3,1\le j\le m)\)表示选择了\(i\)个区间后，以第\(j\)个区间为起点，向右通过相交区间到达最远的点是多少，那么可以写出\(f(i,j)\)的状态转移方程：

\(f(i,j)= \left \{\begin{aligned} &r_j' & & \text{if}\quad i=1 \\ &r_{t(i,j)}' & & \text{if}\quad i>1 \\ \end{aligned}\right.\)

其中，\(t(i,j)\)表示满足最大的\(k:k\le m\land l_k'\le f(i-1,j)\)，也就是说，我们选择左端点在区间\([l_j',f(i-1,j)]\)内的所有区间，并取右端点最大的那一个，这样才能保证右端点是取到最大的。这个过程可以使用双指针法完成。

因此，最终答案为\(\displaystyle{\max_{j=1}^{m}\{f(3,j)-l_j'\}}\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 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=100004;
pi pa[N];
int f[3][N];
int n,m=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&pa[i].X,&pa[i].Y);
    sort(pa+1,pa+n+1,[](pi &a,pi &b){return a.X<b.X||a.X==b.X&&a.Y>b.Y;});
    int pre=0;
    for(int i=1;i<=n;i++){
        if(pa[i].Y>pre){
            pa[++m]=pa[i];
            pre=pa[m].Y;
        }
    }
    for(int j=1;j<=m;j++)
        f[0][j]=pa[j].Y;
    for(int i=1;i<=2;i++){
        for(int j=1,k=-1;j<=m;j++){
            k=max(k,j);
            for(;k<=m&&pa[k].X<=f[i-1][j];++k);
            f[i][j]=pa[k-1].Y;
        }
    }
    int ans=0;
    for(int j=1;j<=m;j++)
        ans=max(ans,f[2][j]-pa[j].X);
    printf("%d\n",ans);
}