USACO 2024 2月铜组 B 题题解

· · 题解

思路

我们可以观察到：在不考虑溢出的情况下，在一段时间内，每一桶牛奶每秒的变化量是一定的，也就是说每一秒丢失的牛奶的数量是一定的，而且只有每秒牛奶都会变多的桶才会溢出，只有每秒牛奶都会变少的桶才可能会倒完。

我们还可以观察到：一桶牛奶倒完后，只会对一桶牛奶每秒的变化量有影响，且这样的变化最多 N 次。

所以，我们可以按照时间按从小到大顺序枚举倒完的牛奶桶，再重新计算每一桶每秒的变化量，并加上在这次上一次变化到这一次变化前这一段损失的数量。

时间复杂度：O(N \log N)。 空间复杂度：O(N)。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 5;

struct Node{
  int x, id;
};

int n, m, a[MAXN], b[MAXN], cnt;
char c[MAXN];
long long ans, sum;
struct cmp{
  bool operator ()(Node i, Node j)const {
    return i.x > j.x;
  }
};
priority_queue<Node, vector<Node>, cmp> que;// 优先队列维护时间顺序
int f(char a){
  if(a == 'L'){
    return -1;
  }else{
    return 1;
  }
}

int main(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> c[i];
    int v = ((i + f(c[i])) % n == 0 ? n : (i + f(c[i])) % n);
    b[v]++;//记录有几个桶给它倒牛奶
  }
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    sum += a[i];
    b[i]--;
    if(b[i] == -1){
      que.push({a[i], i});// 它的牛奶在变少，以后会被倒空
    }else if(b[i] == 1){
      cnt++;// 这个桶每秒会溢出导致损失1升奶
    }
  }
  que.push({m, 0});// 只有m秒
  int time = 0;
  while(!que.empty()){
    Node now = que.top();
    que.pop();
    ans += (now.x - time) * 1ll * cnt;
    time = now.x;
    if(now.id == 0){
      break;// m秒到了，退出
    }else{
      int v = ((now.id + f(c[now.id])) % n == 0 ? n : (now.id + f(c[now.id])) % n);
      b[v]--;
      if(b[v] == 0){
        cnt--;// 这个桶倒空了导致他倒向的桶不再溢出导致损失
      }
      if(b[v] == -1){
        que.push({a[v] + time, v});// 这个桶倒空了导致他倒向的桶的牛奶开始变少
      }
    }
  }
  cout << sum - ans << '\n';// 用总共的减去损失的即为答案
  return 0;
}