Codeforces 1238G. Adilbek and the Watering System

传送门

最关键的想法就是每个位置一定用的是当前能用的最便宜的水，因为到后面可能有更便宜的

然后其他还没用上的水我们也留着，假装此时已经买了，但是如果发现后面有更优的再反悔也不迟

每相邻两个朋友之间我们把最便宜的一些水消耗了

然后考虑有朋友来送水了

设这个朋友的水的最大体积为 $mx$，价格为 $cst$，如果系统完全装得下 $mx$ 的水那么 $\text{我全都要}$ 即可

如果装不下那么看看系统里最贵的那个单位水 $x$，如果价格大于 $cst$ ，那么我们就不要这个 $x$ 了，直接反悔，问就是根本没买过

（有点像网络流里面的反向边...）

那么价格为 $cst$ 的水就可以多一单位了，然后不断重复直到水的价格都小于等于 $cst$ 或者这 $mx$ 单位的水全部加入到系统里面

实际上代码实现的时候并不需要一单位一单位考虑

到了最后可能系统里还剩下一些水，当然也是假装根本没买过就行了（实际上的确没买过 $2333$）

怎么维护的问题自己开心就好了，这里学的官方题解用 $map$ （$map$ 竟然还能这么用）

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<map>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=5e5+;

int Q,n,m,Cap,C0;//Cap是容量

struct dat {

    int t,mx,cst;//每个朋友到达时间,最大水量,单位价值

    dat (int _t=,int _mx=,int _cst=) { t=_t,mx=_mx,cst=_cst; }

    inline bool operator < (const dat &tmp) const {

        return t<tmp.t;

    }

}A[N];

#define fir first

#define sec second

ll solve()

{

    ll ans=;

    map <int,int> mp;

    int now=C0; mp[]=C0;

    // now 是当前系统里的水量

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

    {

        int dis=A[i].t-A[i-].t;//时间差

        // 注意当前处理的时间区间是 [ A[i-1].t , A[i].t ), 左闭右开

        while(dis && !mp.empty())//用当前最便宜的水

        {

            int mx=min( mp.begin()->sec , dis );

            mp.begin()->sec -= mx;

            dis-=mx; now-=mx;

            ans+=1ll*mp.begin()->fir * mx;//用了才计算价钱

            if(!mp.begin()->sec)

                mp.erase(mp.begin());

        }

        if(dis) return -;//没水了

        int New=min( Cap-now , A[i].mx );//多出的水

        now+=New;//加满

        while( New<A[i].mx && !mp.empty() && mp.rbegin()->fir > A[i].cst )//考虑替换原本系统里比较贵的水

        {

            int mx=min( mp.rbegin()->sec , A[i].mx-New );

            mp.rbegin()->sec -= mx;

            New+=mx;

            if(!mp.rbegin()->sec)

                mp.erase( --mp.end() );

        }

        mp[A[i].cst]+=New;

    }

    return ans;

}

int main()

{

    Q=read();

    while(Q--)

    {

        n=read(),m=read(),Cap=read(),C0=read();

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

            A[i].t=read(),A[i].mx=read(),A[i].cst=read();

        A[++n]=dat(m,,);//注意细节

        sort(A+,A+n+);

        printf("%lld\n",solve());

    }

    return ;

}

巴特西

Codeforces 1238G. Adilbek and the Watering System

最新文章

热门文章