得物秋招 2023.08.23 编程题目与题解

发表于 2023-08-23 分类于笔试阅读次数：本文字数： 1.3k 阅读时长 ≈ 1 分钟

1、最少数字

小明用计算机随机生成了\(N\)个正整数，他希望从这\(N\)个数中选取若干个数，使得它们的和等于\(M\)。这些随机生成的数字可能会相同，但是每个数字最多只允许使用一次。

当然这样的选取方案可能不存在，也可能有多个。

现在希望你编写一个程序，能够找出数字个数最少的选取方案，输出对应的最少数字的个数，如果无解输出"No solution"。

输入

单组输入，每组输入\(2\)行。

第\(1\)行包含两个正整数\(N\)和\(M\)，分别表示初始输入的正整数个数和目标数字和\((N\le 10^3,M\le 10^5)\)。

第\(2\)行为\(N\)个正整数，两两之间用空格隔开（每一个正整数均小于等于\(10^5\)）。

输出

输出数字个数最少的选取方案中所包含的最少数字个数，如果无解输出"No solution"。

样例

输入：
5 5
1 3 2 1 1

输出：
2

解答

一道普通的0-1背包问题，每个数字的“价值”视为为\(1\)，“重量”视为它本身即可，最终只需要将“价值”最小化即可。

代码

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

const int M=100004;
int n,m,x,f[M];
int main(){
    scanf("%d %d",&n,&m);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        for(int j=m;j>=x;j--){
            f[j]=min(f[j],f[j-x]+1);
        }
    }
    if(f[m]>n) puts("No solution");
    else printf("%d\n",f[m]);
}

2、开幕式排练

导演在组织进行大运会开幕式的排练，其中一个环节是需要参演人员围成一个环形。演出人员站成了一圈，出于美观度的考虑，导演不希望某一个演员身边的其他人比他低太多或者高太多。

现在给出\(n\)个参演人员的身高，问在他们站成一圈时，相邻演员的身高差的最大值至少是多少？请你帮忙计算。

输入

输入包括两行，第一行有1个正整数，代表人数\(n\)。

第二行有\(n\)个空格隔开的正整数\(h_i\)表示第i个演员的身高。

数据保证\(2\le n\le 10^5,1\le h_i\le 10^9\)。

输出

输出包括一个正整数，表示答案。

样例

输入：
5
2 1 1 3 2

输出：
1

提示：
排为1, 2, 3, 2, 1即可。

输入：
2
10 20

输出：
10

提示：
排为10, 20即可。

解答

假设数组\(h\)已经排好序。那么首先知道，在环上从\(h_1\)沿着两条弧的方向到\(h_n\)所在的位置，身高必定是非递减的，如果递减那么必定不是最优的方案。

接下来先将\(h_1\)添加到这个环上。此后每次添加一个数，要么是添加到从\(h_1\)沿着左边的方向的弧的最后一个元素后面，要么是添加到从\(h_1\)沿着右边的方向的弧的最后一个元素后面。最终添加\(h_n\)，将这两个弧进行合并。

假设现在这两条弧的最后一个元素是\((x,y)\)（注意一开始时是\((h_1,h_1)\)）。那么现在添加\(h_i\)。不失一般性，假设\(x<y\)，那么有：

添加\(h_i\)在\(x\)的后面将会得到\((h_i,y)\)，并且得到身高差\(h_i-x\)；
添加\(h_i\)在\(y\)的后面将会得到\((x,h_i)\)，并且得到身高差\(h_i-y\)。

由于在最后面添加的数都不会小于\(h_i\)，这意味着之后的数\(h\)必定和另一个数相邻（对于情况1是\(y\)，情况\(2\)是\(x\)）。如果选择情况2，以后更大的数必须和\(x\)相邻，产生的解必定不是最优的。因此每个时刻都只能选择情况\(1\)。

因此，整个题目就相当于取\(h\)的每隔一个数的两对数的最大值即可。更形式化的说，这道题对答案为

\[\max\{h_2-h_1,\max_{i=1}^{n-2}\{h_{i+2}-h_i\}\}.\]

代码

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

const int M=100004;
int a[M],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    a[0]=a[1];
    int ans=0;
    for(int i=2;i<=n;i++){
        ans=max(ans,a[i]-a[i-2]);
    }
    printf("%d\n",ans);
}