5539. 牛奶交换 - AcWing题库
y老师的板书
如果是往右循环，且有左循环与之相对头，如图所示，则可以发现，右循环的最后一个和左循环的第一个不会损失，因为分别有其右边和或左边的为它补给，而两端(用红线圈出来的部分)的因为没有补给而损失。所以只需将每一个方向相同R或L的划分为一个整体,剔除不会损失的那一个，将整体中其他的与m取小即可算出每一个整体还剩多少，最后将每一个整体求和即可
const int N = 4e5 + 10;//两倍长度LL n,m;
char s[N];
LL a[N];void solve()
{cin >> n >> m;LL ans = 0;for (int i = 1;i <= n;i ++) cin >> s[i];for (int i = 1;i <= n;i ++) cin >> a[i],ans += a[i];for (int i = 1;i <= n;i ++){s[i + n] = s[i];a[i + n] = a[i];}int k = 1;while(k <= n && s[k] == s[k + 1]) k ++;//找可以分开的点if (k < n)//有切口时，计算损失；没有切口时不会损失而是会一直循环{for (int i = k + 1;i + n - 1<= 2 * n;i ++){int j = i;LL sum = 0;while(j <= k + n && s[j] == s[i]) sum += a[j],j ++;if (s[j - 1] == 'R') sum -= a[j - 1];else sum -= a[i];ans -= min(m,sum);i = j - 1;//i++之后i就指向第一个不同的位置了}}cout << ans << endl;
}