Welcome to “Algorithms and the Beauty of Programming” ↑ pay attention to us!
This article was first published on the wechat official account “Beauty of Algorithms and Programming”. Welcome to follow and learn more about this series of blogs in time.
Problem description
Xiaoming has n cakes to share with his friends for his birthday today. The n cakes (numbered 1 to N) weigh A1, A2… , an. Xiao Ming wants to give each of his friends at least k cakes. Lined up xiao Ming’s friends have to get a cake, for each friend, xiao Ming always will first cake among his own hands minimum number, when the friend to share the cake weighs less than k, continue to give minimum number in the left of the cake to him, until the Ming cake points out or the friend to greater than or equal to the total weight of k.
Input format
The first line of the input contains two integers n, k, with the meaning described above. N positive integers, representing A1, A2… , an.
The output format
Output an integer indicating how many friends got a cake.
The sample input
6 and 9
Sample output
3
The sample description
The first friend got the first three cakes, the second friend got the fourth and fifth cakes, and the third friend got the last cake.
Measure the use case size and convention
For all evaluation cases, 1 ≤ N ≤ 1000, 1 ≤ K ≤ 10000, and 1 ≤ AI ≤ 1000.
Please describe the algorithm of the above program in one sentence. Are there other algorithms that are more efficient? Welcome to leave a message.
\
More interesting articles:
Sichuan Tourism Institute Where2Go team
Wechat: The beauty of algorithms and programming
Long press to identify the QR code to follow us!
Tips: Click on the lower right corner of the page “Write a message” to comment, looking forward to your participation! Welcome to forward!