这次学习的是Google Kick Start的2020回A轮题目,因为我没有在考试时做这套题目,因此在此作为学习,以弥补自身不足。

点击这里→传送门 可以返回到这个系列的List哦

Round A 2020

Problem
There areNN houses for sale. The i-th house costsAiA_i dollars to buy. You have a budget ofBB dollars to spend.

What is the maximum number of houses you can buy?

Input
The first line of the input gives the number of test cases,TT.TT test cases follow. Each test case begins with a single line containing the two integersNN andBB. The second line containsNN integers. The i-th integer isAiA_i, the cost of the i-th house.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of houses you can buy.

Limits
Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤TT ≤ 100.
1 ≤BB ≤ 105.
1 ≤AiA_i ≤ 1000, for all i.

Test set 1
1 ≤NN ≤ 100.

Test set 2
1 ≤NN ≤ 105.

Sample

InputOutput
3
4 100
20 90 40 90Case #1: 2
4 50
30 30 10 10Case #2: 3
3 300
999 999 999Case #3: 0

In Sample Case #1, you have a budget of 100 dollars. You can buy the 1st and 3rd houses for 20 + 40 = 60 dollars.
In Sample Case #2, you have a budget of 50 dollars. You can buy the 1st, 3rd and 4th houses for 30 + 10 + 10 = 50 dollars.
In Sample Case #3, you have a budget of 300 dollars. You cannot buy any houses (so the answer is 0).

Note: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.


代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def Calc():
housesNumber_budget=list(map(int, input().split()))
houseValue=list(map(int, input().split()))

houseValue.sort()
valueSum = 0
for i in range(housesNumber_budget[0]):
valueSum+=int(houseValue[i])
if(valueSum>housesNumber_budget[1]):
i-=1
break
return i+1


def main():
totalNumber=int(input())
for i in range(totalNumber):
print("Case #"+str(i+1)+": "+str(Calc()))

if __name__=="__main__":
main()

Problem
Dr. Patel hasNN stacks of plates. Each stack containsKK plates. Each plate has a positive beauty value, describing how beautiful it looks.

Dr. Patel would like to take exactlyPP plates to use for dinner tonight. If he would like to take a plate in a stack, he must also take all of the plates above it in that stack as well.

Help Dr. Patel pick thePP plates that would maximize the total sum of beauty values.

Input
The first line of the input gives the number of test cases,TT.TT test cases follow. Each test case begins with a line containing the three integersNN,KK andPP. Then,NN lines follow. The i-th line containsKK integers, describing the beauty values of each stack of plates from top to bottom.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum total sum of beauty values that Dr. Patel could pick.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤TT ≤ 100.
1 ≤KK ≤ 30.
1 ≤PPNKN * K.
The beauty values are between 1 and 100, inclusive.

Test set 1
1 ≤NN ≤ 3.

Test set 2
1 ≤NN ≤ 50.

Sample

InputOutput
2
2 4 5
10 10 100 30
80 50 10 50Case #1: 250
3 2 3Case #2: 180
80 80
15 50
20 10

In Sample Case #1, Dr. Patel needs to pickPP = 5 plates:
He can pick the top 3 plates from the first stack (10 + 10 + 100 = 120).
He can pick the top 2 plates from the second stack (80 + 50 = 130) .
In total, the sum of beauty values is 250.

In Sample Case #2, Dr. Patel needs to pickPP = 3 plates:
He can pick the top 2 plates from the first stack (80 + 80 = 160).
He can pick no plates from the second stack.
He can pick the top plate from the third stack (20).
In total, the sum of beauty values is 180.

Note: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.


代码部分

第三部分内容

第四部分内容