简单伪暴力思路（核心思路不到20行）

解题思路:拿到这道题首先感觉很像分组背包，也确实可以是，但在这题是用不了的，因为m范围太大，也没有必要使用。我们不妨考虑暴力思路，我们从1到n便历，代表如果我们就到i位置停止的话算出的最优答案，当然如果能装满m的话（也就是能产生符合题意的答案时）便历到当前位置的总库存必须是大于等于m的，那接下假如说便历到了i位置，总库存也已经不少于m，如何算出该位置的答案？首先你得加上油费，然后呢？然后我们是不是按照价格从小到大购买货物？直到买到m数量产生一个答案，这是很自然的思路，那么很明显我们就需要将之前便历的货物按照价格从小到大收集起来是吧？维持最值常用的结构是什么？是堆。但这里我不使用，因为c++自带map结构，其会按照key值自动从小到大排序，因此我们的代码可以相当简单，每收集到一个合法答案就与之前答案取一个min。那么这个思路看着很暴力对吧，但是实际想想也就是o(nlogn)级别的(便历是n级别，在便历过程中map找出插入位置是logn)，额外空间复杂度也就是map，为o(n)。完全可以过

注意事项:代码注释会交代

参考代码:

#include<bits/stdc++.h>

using namespace std;

using ll= long long;

#define INF 0x3f3f3f3f3f3f3f3fLL

ll ans=INF; //注意初始化

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    ll n,m,o;

    cin>>n>>m>>o;

    ll a[n+1],b[n+1],c[n+1];

    map<ll,ll> mp;

    for(int i=1;i<=n;i++){

        cin>>a[i]>>b[i]>>c[i];

    }

    ll sum=0;//用来记录当前总库存

    ll cost=0;//这个是记录开到当前路程的油费

    for(int i=1;i<=n;i++){

        cost=o*c[i];

        mp[a[i]] += b[i]; //这里不能写insert函数，因为如果那样写的话如果之后便历的时候又遇见一个相同的key值，就会被覆盖

        sum+=b[i];

        if(sum>=m){

            ll cnt=0;

            ll curcost=0;

            for(auto j:mp){

                ll key=j.first; //价格

                ll val=j.second;//库存

                if(cnt+val<m){

                    curcost+=key*val;

                    cnt+=val;

                }else{

                    curcost+=(m-cnt)*key;

                    ans=min(ans,curcost+cost);

                    break;

                }

            }

        }

    }

    if(ans==INF) cout<<"-1"<<endl; //这里注意可能没有合法答案

    else cout<<ans<<endl;

}