【Codeforces 1120F】Secret Letters | Mrsrz's blog

贪心。

题目大意：

有两个人互相送信。

有 $n$ 个事件，第 $i$ 个事件发生在时刻 $t_i$，为 $p_i$ 送信给对方。

对于一次送信，可以直接送过去，花费代价为 $d$，也可以寄存起来。

一封信寄存一个单位时间需要花费 $c$ 的代价。一个人只有在去寄存信的时候，才能取走对方寄存的信。

最后两人会在 $t_{n+1}$ 时刻同时取走所有寄存的信。

求最小的总代价。

题解：

我们考虑第一次将信寄存之后，由于对方需要在寄存信的时候才能取走寄存的信，所以从第一次寄存开始，至少有一封信会一直寄存到最后。

时间轴会被两人分为若干段，其中每一段送信的人相同。

考虑目前已经有一封信寄存的情况。对于每一段，这一段的第一次必然要去寄存（这样能使寄存的信的个数变为 $1$，不会变劣），之后的每次送信可以选择寄存或不寄存。寄存的代价为 $c$ 乘上这个时刻到该段的末尾所经过的时间。取 $\min$ 即可。

那么我们可以从大到小枚举第一次寄存的时刻。当枚举到 $i$ 时，我们已经让 $i+1\sim n$ 的送信人选择了最优方案，考虑完 $i$ 第一次寄存之后，再选择 $i$ 是否要寄存即可。

时间复杂度 $O(n)$。

Code：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+6;
typedef long long LL;
int n,c,d,lt;
LL ans,now;
struct man{
    int t,p;
}a[N];
int nx[N][2];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>c>>d;
    for(int i=1;i<=n;++i){
        int t;char s[5];
        cin>>t>>s;
        a[i]=(man){t,*s=='W'};
    }
    cin>>lt;
    nx[n][0]=nx[n][1]=lt;
    for(int i=n-1;i;--i){
        nx[i][0]=nx[i+1][0];
        nx[i][1]=nx[i+1][1];
        nx[i][a[i+1].p]=a[i+1].t;
    }
    ans=now=(LL)n*d;
    for(int i=n;i;--i){
        now-=d;
        ans=min(ans,now+(LL)c*(lt-a[i].t));
        if(a[i].p==a[i-1].p)now+=min((LL)d,(LL)c*(nx[i][!a[i].p]-a[i].t));
    }
    cout<<ans<<'\n';
    return 0;
}