牛客春招刷题训练营 - 2025.5.27 题解
活动地址:牛客春招刷题训练营 - 编程打卡活动
Easy 小红的整数配对
简要题意
给一个正整数数组,初始有 分。每次可以选数组中两个相差不超过
的数,将它们从数组中删去并获得等于它们乘积的分数,求最大分数。
Solution
排序后总取最大的两个尝试配对,不行就把最大那个丢掉。
Code
void R()
{
int n,k;
i64 ans=0;
cin>>n>>k;
vector<i64> a(n);
for (i64 &x:a) cin>>x;
sort(a.begin(),a.end());
while (a.size()>1)
{
if (a.back()-a[a.size()-2]<=k)
{
ans+=a.back()*a[a.size()-2];
a.pop_back();
}
a.pop_back();
}
cout<<ans;
return;
}
Medium 小红的取模构造
简要题意
给定非负整数 ,构造正整数
,使得:
Solution
分类讨论。
当 时,若
则有解
1 1
,否则无解。
当 时,若
有解
,否则有解
,反之同理。
Code
void R()
{
int a,b;
cin>>a>>b;
if (a==b)
{
if (a==0) cout<<"1 1\n";
else cout<<"-1 -1\n";
}
else if (a<b)
{
if (a==0) cout<<2*b<<' '<<b<<'\n';
else cout<<a+b<<' '<<b<<'\n';
}
else
{
if (b==0) cout<<a<<' '<<2*a<<'\n';
else cout<<a<<' '<<a+b<<'\n';
}
return;
}
Hard 【模板】单源最短路Ⅲ ‖ 非负权图
简要题意
给定一个有 个点
条有向边的非负权图,求单源最短路。
Solution
使用堆优化的 Dijkstra 算法,记得开 long long
记录答案。
Code
void R()
{
using pli=pair<i64,int>;
int n,m,s;
cin>>n>>m>>s;
s--;
vector<vector<pli>> adj(n);
for (int i=0;i<m;i++)
{
int u,v,w;
cin>>u>>v>>w;
u--,v--;
adj[u].push_back({w,v});
}
vector<int> vis(n);
vector<i64> d(n,-1);
priority_queue<pli,vector<pli>,greater<pli>> q;
d[s]=0;
q.push({0,s});
while (!q.empty())
{
auto [tmp,u]=q.top();
q.pop();
if (vis[u]) continue;
vis[u]=1;
for (auto [w,v]:adj[u])
if (d[v]==-1||d[v]>d[u]+w)
{
d[v]=d[u]+w;
q.push({d[v],v});
}
}
for (int i=0;i<n;i++)
cout<<d[i]<<" \n"[i+1==n];
return;
}
#牛客春招刷题训练营#