打卡信奥刷题（3662）用C++实现信奥题 P12187 [蓝桥杯 2025 省 Python A/Java A/研究生组] 原料采购

P12187 [蓝桥杯 2025 省 Python A/Java A/研究生组] 原料采购

题目描述

小蓝负责一家工厂的原料采购。

工厂有一辆运货卡车，其容量为 $m$。

工厂附近的采购点都在同一条路的同一方向上，一共有 $n$ 个，每个采购点和工厂的距离各不相同。其中，第 $i$ 个采购点的价格为 $a_i$, 库存为 $b_i$, 距离为 $c_i$。

卡车每行驶一单位长度的路径就需要额外花费 $o$。（返程没有花费，你也可以认为 $o$ 实际是行驶两单位长度的花费）

请计算将卡车装满最少需要花费多少钱，如果没有任何方案可以装满请输出 $-1$。

输入格式

输入的第一行包含三个正整数 $n,m,o$，相邻整数之间使用一个空格分隔。

接下来 $n$ 行，每行包含三个正整数 $a_i,b_i,c_i$ 表示一个采购点，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案，即装满卡车所需的最小花费。

输入输出样例 #1

输入 #1

3 5 1
99 9 1
3 4 99
1 2 190

输出 #1

201

说明/提示

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$n\le 5000$, $m\le 50000$;
• 对于 $60\%$ 的评测用例，$m\le 10^5$;
• 对于所有评测用例，$1\le n\le 10^5$, $1\le m,o\le 10^9$, $1\le a_i,b_i,c_i\le 10^9$, 保证对于 $i>1$, 一定有 $c_{i-1}<c_i$。

C++实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt,tot;
priority_queue<pair<int,int>>q;
signed main(){
int n,m,o;cin>>n>>m>>o;
int ans=1e18;
for (int i=1;i<=n;++i){
int a,b,c;cin>>a>>b>>c;
tot+=b;
cnt+=a*b;
q.push({a,b});
while(tot>m){
auto t=q.top();q.pop();
int p=t.first,tmp=t.second;
if(tmp<=tot–m){
tot-=tmp;
cnt-=p*tmp;
}else{
cnt-=p*(tot–m);
if(tmp>tot–m)
q.push({p,tmp–tot+m});
tot=m;
break;
}
}
if(tot==m)
ans=min(ans,cnt+o*c);
}
if(ans==1e18)
cout<<–1;
else
cout<<ans;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容