题解——USACO 24FEB B Milk Exchange

yuyc · 2024-02-20 10:32:34 · 题解

题意

有 N 头奶牛围成一圈，第 i 头奶牛有一个容量为 a_i 的桶，初始时桶满，每一时刻，每头奶牛都会根据一个操作序列 s 来将自己桶中的 1 升牛奶倒给自己左边或右边的奶牛（如果桶里有牛奶的话），传递完之后，大于桶的容量那部分牛奶将会溢出，问 M 时刻后，所有的桶里一共还剩多少牛奶。

解析

如果 s_i 是 R，s_{i+1} 是 L，那么我们就将这两个操作方向对应的两头奶牛称为两头 “溢牛”，或一个 “溢牛对”。

为什么这样称呼呢？ 注意到每次操作，溢牛对内部的总奶量不变，因为左边的溢牛总是能给右边的溢牛倒 1 升牛奶，右边的溢牛也总是能给左边的溢牛倒 1 升牛奶，相当于是每次互相交换 1 升牛奶。

这就意味着，只要有牛奶被传递给溢牛对，这部分牛奶必定溢出，因为溢牛对内部奶量总是满的，故对于每一个溢牛对，只需求出可能被传递给它左右边的奶量，分别对 m 取最小值即可求出每个溢牛对溢出的奶量。

其实就是求每个溢牛对左边连续的 R 所对应的奶牛的奶量和右边连续的 L 所对应的奶牛的奶量。

代码

尤其注意奶牛们围成一个圈。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll a[N],b[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    ll ans = 0,sum = 0;
    cin>>n>>m;
    string s;
    cin>>s;
    s = s[n - 1] + s;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum += a[i];    
    }
    for(int i=0;i<=n;i++){
        if(s[i] == 'R' && s[i + 1] == 'L'){
            ll l = 0,r = 0;
            int lpos = i - 1 <= 0 ? i - 1 + n : i - 1,rpos = i + 2 > n ? i + 2 - n : i + 2;
            while(s[lpos] == 'R'){
                l += a[lpos];
                lpos--;
                if(lpos <= 0) lpos += n;
            }
            while(s[rpos] == 'L'){
                r += a[rpos];
                rpos++;
                if(rpos > n) rpos -= n;
            }
//          cout<<l<<' '<<r<<'\n';
            ans += min(m,l) + min(m,r);
        }
    }
    cout<<sum - ans;
    return 0;
}