Problem
Farmer John's () cows are lined up in a circle such that for each in , the cow to the right of cow is cow , and the cow to the right of cow is cow . The th cow has a bucket with integer capacity () liters. All buckets are initially full.
Every minute, the cows exchange milk according to a string consisting solely of the characters ‘’ and ‘’. if the th cow has at least liter of milk, she will pass liter of milk to the cow to her left if ’ , or to the right if ’. All exchanges happen simultaneously (i.e., if a cow has a full bucket but gives away a liter of milk but also receives a liter, her milk is preserved). If a cow's total milk ever ends up exceeding , then the excess milk will be lost.
FJ wants to know: after minutes (), what is the total amount of milk left among all cows?
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains and .
The second line contains a string consisting solely of the characters ‘’ or ‘’, denoting the direction each cow will pass their milk in.
The third line contains integers , the capacities of each bucket.
OUTPUT FORMAT (print output to the terminal / stdout):
Output an integer, the sum of milk among all cows after minutes.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
SAMPLE INPUT:
3 1
RRL
1 1 1
SAMPLE OUTPUT:
2
Cows and pass each other one liter of milk, so their milk is preserved. When cow passes their milk to cow , cow 's bucket overflows, and one liter of milk is lost after one minute.
SAMPLE INPUT:
5 20
LLLLL
3 3 2 3 3
SAMPLE OUTPUT:
14
Each cow is passing a liter of milk to the cow on the left and gaining a liter of milk from the cow on the right, so all of the milk is preserved regardless of how much time passes.
SAMPLE INPUT:
9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4
SAMPLE OUTPUT:
38
Initially, there are a total of 51 liters of milk. After 5 minutes, cows , , and will lose 5, 3, and 5 liters of milk respectively. Therefore, a total of 38 liters of milk remain.
SCORING:
- Inputs 4-8:
- Inputs 9-16: No additional constraints.
Solution
算法与解法
(讲得有可能不清楚,请谅解)
观察题目,发现 倒入右边桶内, 倒入左边桶内,那如果当序列中出现了 ,就代表左边奶牛会给右边 ,右边奶牛会给左边 ,就代表这两个奶牛的瓶子一直保持着满瓶的状态,如果一旦外面有牛奶倒入,就会使瓶子满杯而产生总量损失,也只有这种情况会产生损失。外面有任何牛奶倒入就代表:左边临近的奶牛字符为 ,后边临近的奶牛字符为 。这就说明左/右一定会浪费牛奶,浪费牛奶数应为 ,因为倒牛奶最多有 轮,每轮只能给予一升牛奶, 便是最大值了,但如果奶牛已没有奶了,便无法给予。
但对于每个 输入的数值不仅取决于临近的 与 ,也可能有一下情况:
RRRRRLLLLL
我们会发现中间有一个 ,而左边是 4 个 ,这会引发一个奇妙的现象:最左边的 每轮给予下一个 一升,下一个 会给予再下一个 一升,引发了一个接力,直到将牛奶给予了 。出现了这个“接力”现象,计算浪费牛奶数就有亿点儿困难了,我们可以发现最后一个奶牛会经过接力持续给予牛奶,当没有牛奶时,就需要倒数第二个奶牛给予牛奶;当倒数第二个奶牛没有牛奶时,就需要倒数第三个奶牛给予牛奶……以此类推。根据这个现象,我们可以找到解决方法:从 处往左开始遍历,要求 不断开,则每一个就是 。其实就是将附近的 奶牛所持有的牛奶数累加,最大值不超过 ,找出一共可以给予 多少升牛奶(也就是损失了多少牛奶)。 与以上做法同理,只不过换了一个遍历方向。
综上所述,我们需要找到每个 ,被找到给 提供牛奶的奶牛,计算损失数,把所有损失数从总牛奶数减去,即为答案。
特别要提醒的是:第一只奶牛与第 只奶牛是连起来的,在遍历和寻找 请注意这一点。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 1;
int n, m, res, a[N];
char c[N];
signed main(){
scanf("%lld%lld%s", &n, &m, c);
for(int i = 1;i <= n; i++){
scanf("%lld", &a[i]);
res += a[i]; //计算总牛奶值
}
if(c[0] == 'L' && c[n - 1] == 'R') //第一个与第 n 个形成 RL
c[0] = ' ', c[n - 1] = ' ';
for(int i = 1;i < n; i++)
if(c[i - 1] == 'R' && c[i] == 'L') //i-1 与 i 形成 RL
c[i - 1] = ' ', c[i] = ' '; //用空格代替,以记录
for(int i = 0;i < n; i++){
int suma = 0, sumb = 0; //suma 记录左边相连的奶牛给予牛奶的数量,sumb 则是记录右边的
int l = i - 1;
if(l < 0)
l = n - 1;
if(c[l] != ' ' || c[i] != ' ')
continue ;
bool flag = false;
for(int j = l - 1;j >= 0 && !flag; j--){
if(c[j] == 'R') //是否相连
suma = min(suma + a[j + 1], m);
else
flag = true;
}
if(!flag){ //如果持续相连直到第一个,那就从第 n 个往前检查是否还有相连
for(int j = n - 1;j >= 0 && !flag; j--){
if(c[j] == 'R')
suma = min(suma + a[j + 1], m);
else
flag = true;
}
}
flag = false; //以下同 suma
for(int j = i + 1;j < n && !flag; j++){
if(c[j] == 'L')
sumb = min(sumb + a[j + 1], m);
else
flag = true;
}
if(!flag){
for(int j = 0;j < n && !flag; j++){
if(c[j] == 'L')
sumb = min(sumb + a[j + 1], m);
else
flag = true;
}
}
res -= suma + sumb; //从总牛奶数减去此 RL 损失数
}
printf("%lld", res);
return 0;
}
文章创作了 小时,点个赞再走 ~