c++求解
c++求解
c++求解
Farmer John's cows have quite the sweet tooth, and they especially enjoy eating candy canes! FJ has N
total cows, each with a certain initial height and he wants to feed them M
candy canes, each also of varying height (1≤N,M≤2*10^5)
).
FJ plans to feed the candy canes one by one to the cows, in the order they are given in the input. To feed a candy cane to his cows, he will hang the candy cane so that initially the candy cane is just touching the ground. The cows will then line up one by one, in the order given by the input, and go up to the candy cane, each eating up to their height (since they cannot reach any higher). The candy cane stays suspended in place where it is initially set up and is not lowered to the ground, even after cows eat the bottom of the candy cane. It is possible a cow may eat nothing during her turn, if the base of the candy cane is already above that cow's height. After every cow has had their turn, the cows grow in height by how many units of candy cane they ate, and Farmer John hangs the next candy cane and the cows repeat the process again (with cow 1 again being the first to start eating the next candy cane).
The first line contains N
and M
.
The next line contains the initial heights of the N
cows, each in the range [1,109]
.
The next line contains the heights of the M
candy canes, each in the range [1,109]
.
OUTPUT FORMAT (pipe stdout):
The final heights of each of the N
cows on separate lines.
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 2
3 2 5
6 1
SAMPLE OUTPUT:
7
2
7
The first candy cane is 6
units tall.
The first cow eats the portion of the first candy cane up to height 3
, after which the remaining portion of the first candy cane occupies heights [3,6]
.
The second cow is not tall enough to eat any of the remaining portion of the first candy cane.
The third cow eats two additional units of the first candy cane. The remaining portion of the first candy cane, occupying heights [5,6]
, is not eaten.
Next, each cow grows by the amount she ate, so the heights of the cows become [3+3,2+0,5+2]=[6,2,7]
The second candy cane is 1
unit tall, and the first cow eats all of it.
SCORING:
Inputs 2-10: N,M≤103
Inputs 11-14: No additional constraints.
Problem credits: Agastya Goel
中文翻译
农夫约翰的奶牛很喜欢吃甜食，它们特别喜欢吃棒棒糖!FJ有N
奶牛总数，每头奶牛有一定的初始高度，他想喂它们M
拐杖糖，每根高度也不同(1≤N,M≤2*10^5)
）.
FJ计划按照输入的顺序，把棒棒糖一根一根地喂给奶牛。为了喂他的牛吃拐杖糖，他会把拐杖糖挂起来，这样拐杖糖一开始就会碰到地面。然后，奶牛会按照输入的顺序，一个接一个地排好队，走向棒棒糖，每只都吃到自己的高度(因为它们不能再高了)。即使在奶牛吃掉了棒棒糖的底部之后，棒棒糖也会悬浮在最初设置的地方，而不会降到地面。如果棒棒糖的底部已经高于奶牛的身高，那么奶牛可能在轮到她的时候什么也不吃。在每头奶牛吃完拐杖糖后，奶牛的身高会随着它们吃下的拐杖糖的数量而增长，农夫约翰悬挂下一根拐杖糖，奶牛再次重复这个过程(奶牛1再次成为第一个开始吃下一根拐杖糖的人)。
输入格式(管道stdin):
第一行包含N
和M
．
下一行包含N的初始高度
奶牛，每头都在范围内[1109]
．
下一行包含M的高度
拐杖糖，每一种都在[1109]
．
输出格式(管道标准输出):
每个N的最终高度
奶牛在不同的线上。
注意，这个问题中涉及的大尺寸整数可能需要使用64位整数数据类型(例如，C/ c++中的“long long”)。
样例输入:
3 - 2
3 2 5
6个1
样例输出:
7
2
7
第一根拐杖糖是6
单位高。
第一头牛吃了第一个棒棒糖的一部分，直到3的高度
，之后，第一根棒棒糖手杖的剩余部分占据高度[3,6]
．
第二只牛不够高，吃不了第一只拐杖糖的剩余部分。
第三头牛吃了另外两单位的第一根棒棒糖。第一根拐杖糖的剩余部分，占据高度[5,6]
，是不吃的。
接下来，每头奶牛的身高都随着它吃的量的增加而增加，这样奶牛的身高就变成了[3+3,2+0,5+2]=[6,2,7]
．
第二个棒棒糖是1
单位高，第一头牛把它全吃了。
得分:
输入2-10:N,M≤103
输入11-14:没有额外的约束。
问题归功于:Agastya Goel
