SKIPONE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

There are N items, the i-th one costs A_i coins.
You have K coins in total.

You must buy items in the order 1, 2, \ldots, N.
If you skip buying an item, you can’t buy any future items either.

You have a coupon that can make one item’s price 0.
Find the maximum number of items you can buy.

EXPLANATION:

Suppose we want to buy i items.
Then, due to the constraints of the problem, we must buy items 1, 2, 3, \ldots, i.

We have a coupon that can make one item free - of course, this should be used on the most expensive item.

Thus, we can buy the first i items only if

A_1 + A_2 + \ldots + A_i - \max(A_1, \ldots, A_i) \le K

Our task is to find the largest value of i for which this holds.

This can be done easily in \mathcal{O}(N) by simply storing the sum and maximum value so far.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    ans = 0
    mx, sm = 0, 0
    for i in range(n):
        sm += a[i]
        mx = max(mx, a[i])
        if sm - mx <= k:
            ans = i+1
        else:
            break
    print(ans)