AcWing 5539. 牛奶交换(c纯拓扑排序解法)
原题链接
简单
作者:
宋裕扬
,
2025-03-26 11:49:33
·广东
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll sum;
int n, m;
int a[N], in_degree[N];
string s;
int h[N], e[N], ne[N], idx;
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++, in_degree[b]++;
}
int main(){
memset(h, -1, sizeof h);
cin >> n >> m >> s;
for(int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];
}
for(int i = 0; i < s.size(); i++){
if(s[i] == 'R'){
if(i == n - 1) add(i + 1, 1);
else add(i + 1, i + 2);
} else {
if(i == 0) add(i + 1, n);
else add(i + 1, i);
}
}
vector<int>q;
for(int i = 1; i <= n; i++){
if(in_degree[i] == 0) q.push_back(i);
}
for(int t : q){
int tmp = 0;
queue<int>que;
que.push(t);
while(que.size()){
int x = que.front();
que.pop();
tmp += a[x];
if(tmp >= m){
tmp = m;
break;
}
for(int i = h[x]; i != -1; i = ne[i]){
int j = e[i];
if(--in_degree[j] == 0){
que.push(j);
}
}
}
sum -= tmp;
}
cout << sum << endl;
return 0;
}