美团 秋招 2023.08.26 机试题目与题解

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

1、小美种果树

小美在手机上种果树，只要成熟了就可以领到免费的水果了。

小美每天可以给果树浇水，果树的成长值加\(x\)。同时也可以给果树施肥，两次试飞至少需要间隔\(2\)天，果树的成长值加\(y\)。果树成长值到达\(z\)就成熟了。

小红想知道，最少需要多少天可以领到免费的水果。

输入

一行三个整数\(x,y,z\)，分别表示浇水的成长值，施肥的成长值，果树成熟的成长值。

  • \(1\le x,y,z\le 10^9\)

输出

一行一个整数，表示最少需要多少天可以领到免费的水果。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：
1 2 10

输出：
6

提示：
第一天施肥浇水，成长值为3。
第二天浇水，成长值为3+1=4。
第三天浇水，成长值为4+1=5。
第四天施肥浇水，成长值为5+3=8。
第五天浇水，成长值为8+1=9。
第六天浇水，成长值为9+1=10。
果树成熟了，可以领到免费水果了!

解答

由于每一天的行为都是按照\(3\)为周期来进行循环的，其中这\(3\)天分别可以提升\(x+y,x,x\)的成长值。

考虑将这\(3\)天视为一个整体，那么浇这棵树至少需要\(\left\lfloor\dfrac{z}{3x+y}\right\rfloor\)个完整的周期，这期间一共需要花费\(3\cdot \left\lfloor\dfrac{z}{3x+y}\right\rfloor\)天。接下来还需要一个不完整的周期就能浇完这棵树。从前往后枚举这个周期中的每一天，都浇一次，直到这棵树的成长值达到\(z\)即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll x,y,z;
    scanf("%lld %lld %lld",&x,&y,&z);
    y+=x;
    ll s=y+x+x;
    ll ans=z/s*3;
    vector<ll>v={y,x,x};
    ll nz=z/s*s;
    for(ll t:v){
        if(nz<z){
            ++ans;
            nz+=t;
        }
    }
    printf("%lld\n",ans);
}

2、小红结账

大家一起吃饭的时候，总是小红先付钱，然后大家再把钱转给小红。

现在小红有\(n\)张账单，每张账单记录了有\(k\)个人一起吃饭，以及吃饭的消费\(c\)，现在小红需要计算每个人需要转给小红多少钱。

由于大家都比较喜欢整数，所以大家每张账单会转给小红\(\left\lceil\dfrac{c}{k}\right\rceil\)，\(\left\lceil x\right\rceil\)表示对\(x\)进行上取整。

输入

第一行输入两个整数\(n,m(1\le n,m\le 10^5)\)表示账单数和除小红外的总人数(分别用\(1\)到\(m\)表示)。

换下来\(2\times n\)行，每\(2\)行表示一张账单。对于每张账单：

第一行输入两个整数\(k(2\le k\le m+1),c(1\le c\le 10^9)\)表示一起吃饭的人数，花费。

第二行输入\(k-1\)个整数，表示除小红外有哪些人一起吃饭。

数据保证，\(k\)的总和不超过\(2\times 10^5\)。

输出

输出\(m\)个整数，表示每个人要给小红转账的总金额。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：
2 3
3 10
1 2
4 8
1 2 3

输出：
6 6 2

提示：
第一张账单：第1、2个人都会给小红转4元
第二张账单：第1、2、3个人都会给小红转2元
因此答案为4+2=6，4+2=6，2

解答

简单题意模拟。枚举输入的\(k-1\)个人，将他们的转账金额都加上\(\left\lceil\dfrac{c}{k}\right\rceil\)即可。

为了充分利用向下整除的性质，对于非负整数\(a\)和正整数\(b\)，\(\left\lceil\dfrac{a}{b}\right\rceil\)的值可以用\(\left\lfloor\dfrac{a+b-1}{b}\right\rfloor\)来表示。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
ll c[N];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        int k,all,id;
        scanf("%d %d",&k,&all);
        for(int j=1;j<k;j++){
            scanf("%d",&id);
            c[id]+=(all+k-1)/k;
        }
    }
    for(int j=1;j<=m;j++)
        printf("%lld%c",c[j]," \n"[j==m]);
}

3、小美的游戏

小美有一个长度为\(n\)的数组，她最多可以进行\(k\)次操作，每次操作如下：

  1. 选择两个整数\((1\le i\le j\le n)\)
  2. 选择两个整数\(x,y\)，使得\(x\times y=a_i\times a_j\)
  3. 将\(a_i\)替换为\(x\)，将\(a_j\)替换为\(y\)

她希望晨多进行\(k\)次操作之后，最后数组中的元素的总和尽可能大。

输入

一行两个整数\(n,k\)，表示数组的长度和操作的次数。

一行\(n\)个整数\(a_1,a_2,\dots,a_n\)，表示数组的元素。

  • \(1\le k< n\le 10^5\)
  • \(1\le a_i \le 10^5\)

输出

输出一个整数，表示最后数组中的元素的总和的最大值，由于答案可能很大，你只需要输出答案对\(10^9+7\)取模的结果。

样例

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

输出：
65

提示：
第一次操作后，数组变为[1, 2, 12, 1, 5]
第二次操作，数组变为[1, 2, 60, 1, 1]

解答

这里的结论显而易见，只需要选择\(a\)中最大的\(k+1\)个数，并将它们累乘到同一个数中，就能得到一个最大的积\(M\)。

因此，答案为\(M\)，再加上其余的\(n-k-1\)个最小数数，以及\(k\)次操作后产生的\(k\)个\(1\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
int a[N],n,k;
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1,greater<int>());
    ll ans=1,mod=1e9+7;
    ++k;
    for(int i=1;i<=k;i++){
        ans=ans*a[i]%mod;
    }
    for(int i=k+1;i<=n;i++){
        ans=(ans+a[i])%mod;
    }
    ans=(ans+k-1)%mod;
    printf("%lld\n",ans);
}

4、小美的数组重排

小美有两个长度为\(n\)的数组\(a\)和\(b\)。

小美想知道，能不能通过重排\(a\)数组使得对于任意\(1\le i\le n,1\le a_i+b_i\le m\)？

将会有\(q\)次询问。

输入

第一行一个整数\(q(1\le q\le 30)\)，表示询问次数。

对子每一个询问：

第一行输入两个整数\(n,m(1\le n,m\le 500)\)。

第二行输入\(n\)个整数\(a_i(-500\le a_i\le 500)\)。

第三行输入\(n\)个整数\(b_i(-500\le b_i\le 500)\)。

输出

\(q\)行，每行输出一个字符串，如果能通过重排满足条件则输出"Yes"(不含引号)，否则输出"No"。

样例

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

输出：
No
Yes

提示：
对于第一个用例，无论怎么重排都不满足条件。
对于第二个用例，将数组a重排为[5, 3, -2, 4, -1]时满足条件。

解答

考虑先对\(a\)数组排序，那么在\(a\)数组排完序后，对\(b\)数组中的每个元素\(b_j\)可以处理出一个二元组\([l_j,r_j]\)，用来表示\(\forall i\in [l_j,r_j]\)，都有\(1\le a_i+b_j\le m\)成立。

接下来问题转化成如下：

现在有\(n\)个区间\([l_j,r_j]\)以及从\(1\)到\(n\)这\(n\)个数，每个区间只能放置一个数，考虑将这\(n\)个数放入这\(n\)个区间中，数\(x\)只能放入满足\(l_j\le x\le r_j\)的区间中。问：是否存在一种方法使得所有数都放在区间中？

一个区间\([l_j,r_j]\)能放置数\(i\)以为着\(a_i\)能和\(b_j\)匹配。因此只需要解决转化后的问题即可。

这个具体过程如下，从\(1\)到\(n\)枚举每个数\(x\)，找到能够容纳\(x\)的所有区间，并选择一个右端点最小的区间。如果不存在，那么说明上述的匹配不存在，否则，将这个区间和数\(x\)匹配起来。为什么选择右端点最小的？因为\(1,2,\dots,x-1\)已经匹配上了。左端点只需要不超过\(x\)即可，至于具体是多少，则没有所谓。此外，为了能够让后面的数有机会匹配上，因此才选择最小的右端点。

可以使用二分法处理出所有的\([l_j,r_j]\)，第二部分匹配区间可以使用最小堆进行解决。总的时间复杂度可以达到\(O(n\log n)\)。

代码

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
39
40
41
42
43
44
45
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=104;
int a[N],b[N],n,m;
vector<int>pa[N];
bool solve(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        pa[i].clear();
    for(int i=1;i<=n;i++){
        int l=0,r=0;
        for(int j=1;j<=n;j++){
            int x=a[j]+b[i];
            if(1<=x&&x<=m){
                if(l==0) l=j;
                r=j;
            }
        }
        if(l==0) return 0;
        pa[l].push_back(r);
    }
    priority_queue<int,vector<int>,greater<int>>q;
    for(int l=1;l<=n;l++){
        for(int x:pa[l]) q.push(x);
        if(q.empty()||q.top()<l) return 0;
        q.pop();
    }
    return 1;
}
int main(){
    int Q;
    freopen("r.txt","r",stdin);
    scanf("%d",&Q);
    while(Q--){
        puts(solve()?"Yes":"No");
    }
}

5、平均数为\(k\)的最长连续子数组

给定\(n\)个正整数组成的数组，求平均数正好等于\(k\)的最长连续子数组的长度。

输入

第一行输入两个正整数\(n\)和\(k\)，用空格隔开。 第二行输入\(n\)个正整数\(a_i\)，用来表示数组。

  • \(1\le n\le 200000\)
  • \(1\le k,a_i\le 10^9\)

输出

如果不存在任何一个连续子数组的平均数等于\(l\)，则输出\(-1\)。

否则输出平均数正好等于\(k\)的最长连续子数组的长度。

样例

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

输出：
3

提示：
取前三个数即可，平均数为2。

解答

如果一个子数组的平均值为\(k\)，那么对于一个子数组\(a[l:r](1\le l\le r\le n)\)，有\(\dfrac{\sum_{i=l}^r a_i}{r-l+1}=k\)，经过转化后，可以得到\(\displaystyle{\sum_{i=l}^r(a_i-k)=0}\)。

因此构造子数组\(b_i=a_i-k\)，只需要找到\(b\)中一个和为\(0\)的最长子数组即可。

令\(\displaystyle{s_j=\sum_{i=1}^jb_i}\)，即\(s\)是\(b\)的前缀和，其中\(s_0=0\)。对于每个\(i\in[1,n]\)，只需要在\([0,i)\)中找到一个最小的\(j\)，使得\(s_j=s_i\)即可，这时\(b[j+1:i]\)是一个和为\(0\)，且以\(i\)为右端点的子数组。使用哈希表记录相同的\(s_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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=200004;
ll a[N],s[N];
int n,k;
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]-=k;
        s[i]=s[i-1]+a[i];
    }
    unordered_map<ll,int>mp;
    mp[0]=0;
    int ans=-1;
    for(int i=1;i<=n;i++){
        if(mp.count(s[i])){
            ans=max(ans,i-mp[s[i]]);
        }
        else{
            mp[s[i]]=i;
        }
    }
    printf("%d\n",ans);
}
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝