当前位置：首页 > backend >正文

2025/5/28 考试和答疑。

backend 2025/7/27 17:59:50

本次考试一共考了2道题。一道是基础算法，另外1道是2分

第一题。

A. B - Job Assignment (AI)

问题陈述

你的公司有N名员工，分别称为员工1至N。

你收到了两个工作订单，分别为工作A和B，必须完成它们。

员工i可以在A_i分钟内完成工作A，在B_i分钟内完成工作B。

你将为每项工作指派一名员工。

你可以将两项工作都指派给同一名员工，在这种情况下，他/她完成它们所需的时间是他/她单独完成它们所需时间的和。

如果你将工作指派给不同的员工，他们完成它们所需的时间是他们各自完成工作所需时间中的较长者。

找出完成这些工作所需的最短可能时间。

约束条件

2 \le N \le 10002≤N≤1000
1 \le A\_i \le 10^51≤A_i≤105
1 \le B\_i \le 10^51≤B_i≤105
输入中的所有值都是整数。

输入

输入将通过标准输入以以下格式给出：

A_1A1 B_1B1

A_2A2 B_2B2

A_3A3 B_3B3

\hspace{15pt} \vdots⋮

A_NAN B_NBN

输出

打印完成这些工作所需的最短可能时间，单位为分钟。

示例输入1

8 5

4 4

7 9

示例输出1

如果你将工作A指派给员工2，将工作B指派给员工1，他们将分别在4分钟和5分钟内完成它们。

由于你将工作指派给了不同的员工，两项工作完成所需的时间为\max(4, 5) = 5max(4,5)=5分钟。

不可能再早完成了。

示例输入2

11 7

3 2

6 7

示例输出2

将两项工作都指派给员工2是最佳选择。

注意，如果你将两项工作都指派给同一名员工，他/她完成它们所需的时间是他/她单独完成它们所需时间的和。

这道题其实一开始我读题用了一段时间。

后来我理解到其实这道题就是求一个最佳方案。

如果a问题和b问题的，呃，做的最快的人不是同一个人。的话，那么就找最大的。

如果是同一个人的话，那么就把他们俩时间加起来。

我最开始的代码如下，

#include<bits/stdc++.h>
using namespace std;
int n,a[1010],b[1010],maxx=9999999,maxx1=9999999,maxx12=9999999,a1,b1,a2,b2;
int main()
{
//   freopen("mnotes..in","r",stdin);
//   freopen("mnotes..out","w",stdout);
   cin>>n;
   for(int i=1;i<=n;i++)
   {
       cin>>a[i]>>b[i];
   }
   for(int i=1;i<=n;i++)
   {
       if(a[i]<maxx)
       {
           maxx=a[i];
           a1=i;
       }
   }
   for(int i=1;i<=n;i++)
   {
       if(b[i]<maxx12)
       {
           maxx12=b[i];
           b1=i;
       }
   }

if(a1!=b1)
cout<<max(maxx1,maxx);

else

cout<<maxx12+maxx;
return 0;
}

但是后面我发现

这种代码对样例一不实用。

所以我又给他加了一个for循环判断。

我最终思想

首先我想找出做a工作时间最短的人。

不然后呢再找出做b工作，工作时间最短的人以及嗯除了aA的下标以外，其他做工作最快的人。

最后再判断一下。A做工作最快，最短的时间和除他以外工作比最快的人做个比较。

取最大值。然后呢用这个纸和a做a最快的人加上币最快的人的速度。

取最小值。

最终代码如下，

#include<bits/stdc++.h>
using namespace std;
int n,a[1010],b[1010],maxx=9999999,maxx1=9999999,maxx12=9999999,a1,b1,a2,b2;
int main()
{
//   freopen("mnotes..in","r",stdin);
//   freopen("mnotes..out","w",stdout);
   cin>>n;
   for(int i=1;i<=n;i++)
   {
       cin>>a[i]>>b[i];
   }
   for(int i=1;i<=n;i++)
   {
       if(a[i]<maxx)
       {
           maxx=a[i];
           a1=i;
       }
   }
   for(int i=1;i<=n;i++)
   {
       if(b[i]<maxx1&&a1!=i)
       {
           maxx1=b[i];
           b1=i;
       }
   }
   for(int i=1;i<=n;i++)
   {
       if(b[i]<maxx12)
       {
           maxx12=b[i];
           b1=i;
       }
   }
   cout<<min(max(maxx1,maxx),maxx12+maxx);
   return 0;
}

第二题

. 例题4.3.1 音阶

题目描述

FJ准备教他的奶牛们弹一首歌. 这首歌由N (1 <= N <= 50,000)个音阶组成，第i个音阶要敲击 B_i (1<= B_i <= 10,000) 次。奶牛从第0时刻开始弹，因此他从0时刻到B_1 - 1 时刻都是敲第1个音阶，然后他从 B_1 时刻到B_1 + B_2 - 1时刻敲第2个音阶，从B_1 + B_2时刻到B_1 + B_2 + B_3- 1时刻敲第3个音阶…现在有Q (1 <= Q <= 50,000) 个问题,在时间段区间 [T, T+1)内,奶牛敲的是哪个音阶? 其中 T_i (0 <= T_i <= 整首歌的总时刻).

看下面的一首歌,第1个音阶持续2个单位时间, 第2个音阶持续1个单位时间,第3个音阶持续3个单位时间:

以下是一些询问和回答:

cellpadding="10">

</thead>

询问	回答的音阶
2	2
3	3
4	3
0	1
1	1

输入格式

第 1 行:两个整数: N 、Q。

第 2..N+1行: 第i+1行只有一个整数: B_i

第N+2..N+Q+1行: 第N+i+1行只有一个整数: T_i

输出格式

一行，一个整数，表示答案。

样例数据

input


3 521323401

Copy

output

Copy

数据规模与约定

时间限制：1 \text {s}1s

空间限制：256 \text {MB}256MB

这道题其实就是求每个音的临界值，然后呢看看这个给出的值是否在这个临界值里边儿就行了。

代码如下，

#include<bits/stdc++.h>
using namespace std;
int n,q,a[50010],sum,x,b;
int main()
{
   freopen("mnotes..in","r",stdin);
   freopen("mnotes..out","w",stdout);
   cin>>n>>q;
   for(int i=1;i<=n;i++)
   {
       cin>>x;
       sum+=x;
       a[i]=sum-1;
   }

   for(int i=1;i<=q;i++)
   {
       cin>>b;
       cout<<lower_bound(a+1,a+1+n,b)-a<<endl;
   }
   return 0;
}