蚂蚁集团秋招 2023.09.19 编程题目与题解

发表于 2023-09-25 分类于笔试阅读次数：本文字数： 2.3k 阅读时长 ≈ 2 分钟

1、最优化存储（四）

支付宝服务亿级消费者，每个支付宝的用户有自己独特的信息，假设每个会员存储的成本为\(a_i\)，现在有\(n\)个会员，和一块存储容器\(m\)，希望用该容器存储更多的会员信息；

存储优化是个相当复杂的过程，为了简化问题，存储规则如下：

每个会员的存储成本可以用长度\(a_i\)的线段表示。存储容器一块，可以用一段线段\(m\)表示。

存储容器有个特性，如果会员\(i\)存储在容器中间位置，存储成本为\(a_i\)本身，但是线段容器两端有存储压缩技术，存储在靠两端位置的会员存储成本可以压缩到一半，即 \(a_i/2\)，而且每个会员只能压缩一次。

现在\(n\)个会员，每个会员存储成本为\(a_i\)，以及有一块存储资源，希望你做存储优化，使用尽可能小的存储容器存储下所有会员的信息。

输入

第一行输入一个正整数\(n\)，代表会员的数量。第二行输入\(n\)个正整数\(a_i\)，代表每个会员信息的大小。

\(1\le n \le 10^5\)
\(2 \le a_i\le 10^9\)
保证\(a_i\)是偶数。

输出

一个正整数，代表使用的存储容器大小的最小值。

样例

输入：
5
2 4 4 8 2

输出：
14

提示：
将第三个、第四个会员放在两端即可。使用一个大小为14的容器即可存储全部会员信息。

解答

按照贪心的思想，只需要将最大的两个放在两端，其余的放在中间即可，节省的空间将是最大的。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100004],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    ll ans=a[n-1]/2+a[n]/2;
    for(int i=1;i<n-1;i++)
        ans+=a[i];
    printf("%lld\n",ans);
}

2、小红合并数组

小红有一个长度为\(n\)的数组，每次操作她可以选择一个\(i\)，将\(a_i\)加到\(a_{i-1}\)或者\(a_{i+1}\) (如果\(i-1\)或者\(i+1\)在下标范围内)，请问最少需要多少次操作，可以使数组的所有元素相等。

输入

一行一个整数\(n\)，表示数组的长度。

接下来一行\(n\)个整数\(a_1,a_2,\dots, a_n\)表示数组的初始值。

\(1\le n \le 10^3\)
\(0 \le a_i \le 10^4\)

输出

输出一个整数，表示最少的操作次数。

样例

输入：
5
1 4 2 3 5

输出：
2

提示：
第一次操作，将a2加到a1，数组变为[5,2,3,5]。
第二次操作，将a2加到a3，数组变为[5,5,5]。

解答

更具体的说，这种操作是将相邻的两个数进行合并。令\(\displaystyle{s_i=\sum_{j=1}^i a_i,s_0=0}\)表示数组\(a\)的前缀和。如果最终数组元素都相等，假设这些元素都是\(x\)，最终的长度为\(m(m\le n)\)，那么必定满足\(x\cdot m=s_n\)。

因此，我们可以枚举\(s_n\)所有不超过\(n\)的因子\(d\)，那么说明\(d\)是最终数组可能的长度，\(s_n/d\)是最终数组的每个元素。

在前缀和的角度来看，合并操作仅仅是删除了\(s_1,s_2,\dots,s_{n-1}\)中的某些元素。因此，令\(x=s_n/d\)，我们只需要查看\(x,2x,\dots,dx\)是否为\(s_1,s_2,\dots,s_n\)的一个子序列即可。如果是，那么找到这样最大的\(d\)，并返回最小操作数\(n-d\)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1004;
int a[N],s[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    int m=s[n];
    vector<int>div;
    for(int i=n;i>=1;i--){
        if(m%i==0){
            div.push_back(i);
        }
    }
    int ans=0;
    for(int d:div){
        int w=m/d,c=1;
        for(int i=1;i<=n;i++){
            if(s[i]==c*w){
                ++c;
            }
        }
        if(c>d){
            ans=n-d;
            break;
        }
    }
    printf("%d\n",ans);
}

3、小红的w五元组

小红拿到了一个数组\(a_1,a_2,\dots,a_n\)，她想知道有多少组\((i,j,k,h,l)\)为"w五元组"：

第一、三、五个数相等。第二个数和第四个数相等，且第一个数大于第二个数。用数学语言描述：

\(1\le i< j< k< h< l\le n\)
\(a_i=a_k=a_l\)且\(a_j=a_h\)且\(a_i=a_j\)

输入

第一行输入一个正整数\(n\)，代表数组的元素个数。

第二行输入\(n\)个正整数\(a_i\)，代表小红拿到的数组。

\(5\le n,a_i\le 3000\)

输出

w五元组的数量。由于答案可能太大，请对\(10^9+7\)取模后输出。

样例

输入：
7
3 1 3 1 3 1 3

输出：
6

提示：
6个w五元组分别为（下标表示）：
(1,2,3,4,5)
(1,2,3,4,7)
(1,2,3,6,7)
(1,2,5,6,7)
(1,4,5,6,7)
(3,4,5,6,7)

解答

我们枚举原数组中两个不同的数\(x,y(x>y)\)，并且将要么是\(x\)，要么是\(y\)的这一些元素重新组成一个相对顺序不变的子序列，并将所有\(x\)替换成\(1\)，将\(y\)替换成\(0\)，那么我们得到了一个01比特序列\(b\)，假设其长度为\(m\)。我们将这个问题转化成了：\(b\)中有多少个子序列是\(c=[1,0,1,0,1]\)？

这是一个经典的动态规划问题，令\(f(i,j)(1\le i\le 5,1\le j\le m)\)以\(b-j\)为最后一个元素的子序列，有多少个是\(c_1,c_2,\dots,c_i\)。我们不难写出\(f(i,j)\)的状态转移方程：

\(f(i,j)= \left \{\begin{aligned} &1 & & \text{if}\quad i=1\land b_j=c_1 \\ &\sum_{k=1}^{j-1} f(i-1,k) & & \text{if}\quad i>1\land b_j=c_i \\ &0 & & \text{if}\quad b_j\neq c_i \\ \end{aligned}\right.\)

其中，方程第二行表示对于所有\(f(i-1,k)\)满足的序列，都添加一个元素\(b_j\)，那么就变成了\(f(i,j)\)中满足的子序列。

因此，最终答案为\(\displaystyle{\sum_{j=1}^m f(5,j)}\)。我们可以用\(O(m)\)的时间对这个问题进行求解。

回到原问题，我们枚举一对对不同的\((x,y)\)，并将它们转化成一个01比特序列可以在\(O(m)\)时间内完成（因为这里只需要合并两个有序列表），由于不同的元素都会被组合一次，加上每次求解时都是线性时间的复杂度\(O(m)\)，因此原问题的时间复杂度为\(O(n^2)\)，足够完成。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3004,INF=1<<30;
int n,x;
ll mod=1e9+7;
ll solve(vector<int>&a,vector<int>&b){
    vector<int>v;
    for(int p=0,q=0;!(a[p]==INF&&b[q]==INF);){
        if(a[p]<b[q]) v.push_back(0),p++;
        else v.push_back(1),q++;
    }
    int n=5,m=v.size();
    vector<vector<ll>>f(n,vector<ll>(m));
    for(int j=0;j<m;j++){
        if(v[j]==0) f[0][j]=1;
    }
    for(int i=1;i<5;i++){
        ll tp=0;
        for(int j=0;j<m;j++){
            if(v[j]==(i&1)) f[i][j]=tp;
            tp=(tp+f[i-1][j])%mod;
        }
    }
    ll sum=0;
    for(int j=0;j<m;j++)
        sum=(sum+f[n-1][j])%mod;
    return sum;
}
int main(){
    scanf("%d",&n);
    unordered_map<int, vector<int>>mp;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        mp[x].push_back(i);
    }
    vector<vector<int>>ls;
    for(auto &[k,v]:mp){
        v.push_back(INF);
        ls.emplace_back(v);
    }
    ll ans=0;
    for(int i=0;i<ls.size();i++){
        for(int j=0;j<i;j++){
            ans+=solve(ls[i],ls[j]);
        }
    }
    printf("%lld\n",ans);
}