AT_abc188_d 题解

· · 题解

题目传送门

思路

首先不难想到暴力思路。将所有的钱都加在每一天上，并遍历每一天，如果当天所用金额大于会员价，就开会员卡。

然后这样做会超时。题目中说从 a_i 天到 b_i 天，每天都要支付 c_i 元，考虑差分。但是 a_i,b_i\le10^9，可以使用 map 储存。

这样做的时间复杂度是 \mathcal{O}(N\log N)，可以通过此题。

注意事项

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
map<int,int>mp;
signed main(){
    int n=read(),c=read();
    while(n--){
        int a=read(),b=read(),c=read();
        mp[a]+=c,mp[b+1]-=c;
    }
    int ans=0,sum=0,p=0;
    for(auto i:mp){
        ans+=(i.first-p)*min(sum,c);
        p=i.first;
        sum+=i.second;
    }
    printf("%lld\n",ans);
    return 0;
}