当前位置: 首页> 娱乐> 明星 > 上海市计算机学会竞赛平台2024年1月月赛丙组最大的和

上海市计算机学会竞赛平台2024年1月月赛丙组最大的和

时间:2025/7/11 1:24:53来源:https://blog.csdn.net/a121677_/article/details/139497758 浏览次数:0次
题目描述

给定两个序列 𝑎1,𝑎2,…,𝑎𝑛a1​,a2​,…,an​ 与 𝑏1,𝑏2,…,𝑏𝑛b1​,b2​,…,bn​,请从这两个序列中分别各找一个数,要求这两个数的差不超过给定的数字 𝑑d,且两个数字之和最大

输入格式
  • 第一行:两个整数 𝑛n 与 𝑑d;
  • 第二行:𝑛n 个整数 𝑎1,𝑎2,…,𝑎𝑛a1​,a2​,…,an​;
  • 第三行:𝑛n 个整数 𝑏1,𝑏2,…,𝑏𝑛b1​,b2​,…,bn​;
输出格式
  • 单个整数:两个数的最大和。若没有合适的方案输出 None
数据范围
  • 对于 30%30% 的数据,1≤𝑛≤2001≤n≤200;
  • 对于 60%60% 的数据,1≤𝑛≤200001≤n≤20000;
  • 对于 100%100% 的数据,1≤𝑛≤200001≤n≤20000,1≤𝑑≤1091≤d≤109,1≤𝑎𝑖,𝑏𝑖≤1091≤ai​,bi​≤109。
样例数据

输入:

3 2
3 1 4
1 5 9

输出:

9

说明:

4+5

详见代码:

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[200005];
long long b[200005];
long long d;
long long ans=0;
int main()
{cin>>n>>d;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];}sort(a+1,a+n+1);sort(b+1,b+n+1);int bp=1;for(int i=1;i<=n;i++){while((b[bp]<a[i]||b[bp]-a[i]<=d)&&bp<=n){bp++;}if (b[bp-1]>=a[i]&&bp-1<=n&&b[bp-1]-a[i]<=d){ans=max(ans,a[i]+b[bp-1]);}}int ap=1;for(int i=1;i<=n;i++){while((a[ap]<b[i]||a[ap]-b[i]<=d)&&ap<=n){ap++;}if (a[ap-1]>=b[i]&&ap-1<=n&&a[ap-1]-b[i]<=d){ans=max(ans,b[i]+a[ap-1]);}}if (ans==0){cout<<"None";}else{cout<<ans;}return 0;
}

关键字:上海市计算机学会竞赛平台2024年1月月赛丙组最大的和

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: