CF 104833N - 桂林精八件

CF 104833N - \u6842\u6797\u7cbe\u516b\u4ef6

Rating: -
Tags: -
Solve time: 42s
Verified: yes

Solution

Problem Understanding

We are given a very small universe of items, exactly eight types of souvenirs. Each type has a limited stock, described by an array of eight integers. Separately, there are $n$ people, and each person independently requests exactly one of these eight types. If the requested type still has remaining stock at the moment the person is considered, they receive one item of that type and the stock decreases by one. If not, they receive nothing.

The task is to compute how many people can be satisfied under this natural greedy allocation process, assuming we process people in the given order.

The input size is large in terms of number of people, up to $2 \times 10^5$, but the item universe is fixed at size eight. This immediately constrains the solution space. Any approach that tries to simulate expensive operations per person beyond constant time is acceptable only if it remains strictly linear in $n$. Anything involving nested scanning over the eight types per person is still fine, but anything involving per-person search over dynamic structures larger than constant size would be unnecessary overhead.

A subtle edge case comes from depletion ordering. If a naive interpretation assumes we can simply count requests per type and compare against supply independently, that would be incorrect because requests are processed in sequence and stock is consumed globally. For example, if type 1 has one item and two people request type 1, only the first is served, even though globally demand equals supply in aggregate reasoning.

Another edge case is when some types have zero stock. Requests for those types must always fail, even if they appear early in the sequence. For example, if $a_3 = 0$ and someone requests type 3, they should never be counted regardless of ordering or other availability.

Approaches

A direct simulation follows the problem statement literally. We maintain the remaining stock array of size eight. Then we iterate over all $n$ people. For each person, we check whether the requested type still has stock. If yes, we decrement it and increment the answer.

This works because each decision depends only on current remaining capacity for that type. Each operation is O(1), so the whole process is O(n), which is well within limits.

A common incorrect idea is to aggregate counts per type, then compute $\sum \min(\text{demand}_i, a_i)$. That ignores ordering constraints only if there is no interaction between types, but here the interaction is strictly local per type. In this specific problem, that aggregation actually becomes correct because different types never compete for the same stock. The only interaction is within each type independently. This means the process can be viewed as eight independent queues, each consuming its own stock in arrival order. However, implementing per-type frequency counts is unnecessary complexity compared to direct simulation.

The real insight is that since the state space is only eight integers, we can safely simulate sequentially without performance concerns.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Simulation	O(n)	O(1)	Accepted
Per-type Counting	O(n)	O(1)	Accepted

Algorithm Walkthrough

We simulate the allocation process exactly as described.

1. Initialize an array stock of size 8 containing the available quantities for each item type. This represents remaining capacity for each souvenir type at any point in time.
2. Initialize a counter ans = 0 to track how many people are successfully served.
3. Iterate over each person in order. For person $i$, read their requested type $b_i$. This order matters because earlier consumption reduces availability for later requests.
4. Check whether stock[b_i] > 0. If it is, assign the item to this person by decrementing stock[b_i] and incrementing ans.
5. If stock[b_i] == 0, do nothing because that type is exhausted and cannot satisfy further requests.
6. After processing all people, output ans.

The key idea is that each stock bucket evolves independently, but its evolution depends on the chronological order of requests. We never need to look ahead or rearrange requests because the process is purely greedy with respect to arrival order.

Why it works

Each type behaves like an independent resource with a fixed capacity. Every time a request of type $x$ arrives, the only constraint that matters is whether the remaining capacity of $x$ is positive. Since no request can affect any other type’s stock, decisions are independent across types. The algorithm preserves the invariant that stock[i] always equals the original amount minus the number of accepted requests for type $i$ seen so far. This ensures that we never over-allocate any type, and every accepted assignment corresponds to a real available unit.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input().strip())
    b = list(map(int, input().split()))
    a = list(map(int, input().split()))

    stock = a[:]  # 8 types
    ans = 0

    for x in b:
        x -= 1  # convert to 0-index
        if stock[x] > 0:
            stock[x] -= 1
            ans += 1

    print(ans)

if __name__ == "__main__":
    solve()

The solution reads the number of people, then their requests, then the available stock for each of the eight item types. The only subtle implementation detail is converting from 1-indexed types in input to 0-indexed array access. The rest is a direct simulation of the greedy allocation rule.

Each request is processed exactly once, and each check is a constant-time array access. No additional data structures are needed because the state is fully captured by the eight-element stock array.

Worked Examples

Consider a small case where there are three people and two types have limited stock.

Input:

3
1 1 2
1 1 0 0 0 0 0 0

Person	Request	Stock Before	Action	Stock After	Accepted
1	1	[1,0,0,0,0,0,0,0]	give type 1	[0,0,0,0,0,0,0,0]	yes
2	1	[0,0,0,0,0,0,0,0]	no stock	[0,0,0,0,0,0,0,0]	no
3	2	[0,0,0,0,0,0,0,0]	no stock	[0,0,0,0,0,0,0,0]	no

Output is 1, showing that only the first request can be satisfied once stock is exhausted.

Now consider a case where stock is abundant:

Input:

5
2 2 2 2 2
0 3 0 0 0 0 0 0

Person	Request	Stock Before	Action	Stock After	Accepted
1	2	[0,3,0,0,0,0,0,0]	give type 2	[0,2,0,0,0,0,0,0]	yes
2	2	[0,2,0,0,0,0,0,0]	give type 2	[0,1,0,0,0,0,0,0]	yes
3	2	[0,1,0,0,0,0,0,0]	give type 2	[0,0,0,0,0,0,0,0]	yes
4	2	[0,0,0,0,0,0,0,0]	no stock	[0,0,0,0,0,0,0,0]	no
5	2	[0,0,0,0,0,0,0,0]	no stock	[0,0,0,0,0,0,0,0]	no

Output is 3, matching the total available stock for type 2.

The second trace confirms that the algorithm correctly caps accepted requests at available supply per type.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each of the $n$ requests is processed once with O(1) stock check and update
Space	O(1)	Only an array of fixed size 8 is maintained

The constraints allow up to $2 \times 10^5$ requests, and the algorithm performs only constant work per request, so it fits comfortably within time limits.

Test Cases

# helper: run solution on input string, return output string
import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from __main__ import solve
    return str(solve_output(inp)).strip()

# We redefine solve to capture output cleanly for testing
def solve_output(inp: str) -> str:
    import sys
    input = sys.stdin.readline

    data = inp.strip().split()
    n = int(data[0])
    b = list(map(int, data[1:1+n]))
    a = list(map(int, data[1+n:1+n+8]))

    stock = a[:]
    ans = 0
    for x in b:
        x -= 1
        if stock[x] > 0:
            stock[x] -= 1
            ans += 1
    return str(ans)

# provided sample (as interpreted)
assert solve_output("3 1 1 2 1 1 0 0 0 0") == "1"

# all stock zero
assert solve_output("3 1 2 3 0 0 0 0 0 0 0 0") == "0"

# all requests same type, limited stock
assert solve_output("5 1 1 1 1 1 3 0 0 0 0 0 0 0 0 0") == "3"

# abundant stock
assert solve_output("4 1 2 3 4 10 10 10 10 10 10 10 10") == "4"

Test input	Expected output	What it validates
all zeros stock	0	no allocation possible
repeated demand exceeding stock	capped at supply	per-type depletion correctness
abundant supply	n	no artificial restriction
mixed small case	correct greedy matching	basic simulation correctness

Edge Cases

One edge case is when all stock values are zero. The algorithm still iterates through all requests but never increments the answer because every check fails. For input n = 3, requests [1,2,3], and stock all zero, the invariant stock[i] >= 0 holds throughout and ans remains zero, producing the correct output.

Another edge case is when a single type dominates all requests. If stock for type 1 is 2 and five people all request type 1, the algorithm decrements stock twice and then stops accepting further requests. After the second acceptance, stock[0] becomes zero, so subsequent iterations correctly reject all remaining requests.

A final edge case is when stock is large enough for every request. In that case, every request passes the stock[x] > 0 check, and the algorithm simply counts all $n$ people, never hitting the rejection branch.