CF1009A.Game Shopping

入门

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Maxim wants to buy some games at the local game shop. There are nn games in the shop, the ii-th game costs cic_i.

Maxim has a wallet which can be represented as an array of integers. His wallet contains mm bills, the jj-th bill has value aja_j.

Games in the shop are ordered from left to right, Maxim tries to buy every game in that order.

When Maxim stands at the position ii in the shop, he takes the first bill from his wallet (if his wallet is empty then he proceeds to the next position immediately) and tries to buy the ii-th game using this bill. After Maxim tried to buy the nn-th game, he leaves the shop.

Maxim buys the ii-th game if and only if the value of the first bill (which he takes) from his wallet is greater or equal to the cost of the ii-th game. If he successfully buys the ii-th game, the first bill from his wallet disappears and the next bill becomes first. Otherwise Maxim leaves the first bill in his wallet (this bill still remains the first one) and proceeds to the next game.

For example, for array c=[2,4,5,2,4]c = [2, 4, 5, 2, 4] and array a=[5,3,4,6]a = [5, 3, 4, 6] the following process takes place: Maxim buys the first game using the first bill (its value is 55), the bill disappears, after that the second bill (with value 33) becomes the first one in Maxim's wallet, then Maxim doesn't buy the second game because c2>a2c_2 \gt a_2, the same with the third game, then he buys the fourth game using the bill of value a2a_2 (the third bill becomes the first one in Maxim's wallet) and buys the fifth game using the bill of value a3a_3.

Your task is to get the number of games Maxim will buy.

马克西姆想在当地的游戏商店购买一些游戏。商店里共有 nn 款游戏,其中第 ii 款游戏的价格为 cic_i。

马克西姆的钱包可表示为一个整数数组。他的钱包里有 mm 张纸币,其中第 jj 张纸币的面值为 aja_j。

商店里的游戏从左到右依次排列,马克西姆按此顺序尝试购买每一款游戏。

当马克西姆站在商店中第 ii 个位置时,他从钱包中取出第一张纸币(若钱包为空,则立即前往下一个位置),并尝试用这张纸币购买第 ii 款游戏。在马克西姆尝试购买完第 nn 款游戏后,他离开商店。

马克西姆成功购买第 ii 款游戏,当且仅当他从钱包中取出的第一张纸币的面值大于或等于第 ii 款游戏的价格。若他成功购买了第 ii 款游戏,则该纸币从钱包中消失,下一张纸币成为钱包中的第一张;否则,该纸币保留在钱包中(仍为第一张),马克西姆继续前往下一款游戏。

例如,对于价格数组 c=[2,4,5,2,4]c = [2, 4, 5, 2, 4] 和纸币数组 a=[5,3,4,6]a = [5, 3, 4, 6],整个过程如下:马克西姆用第一张纸币(面值为 55)购买了第一款游戏,该纸币消失;随后第二张纸币(面值为 33)成为钱包中的第一张;接着由于 c2>a2c_2 > a_2,他未能购买第二款游戏;同理,他也未能购买第三款游戏;之后,他用面值为 a2a_2 的纸币(此时第三张纸币已成为钱包中的第一张)购买了第四款游戏,并用面值为 a3a_3 的纸币购买了第五款游戏。

你的任务是计算马克西姆最终将购买多少款游戏。

输入格式

The first line of the input contains two integers nn and mm (1≤n,m≤10001 \le n, m \le 1000) — the number of games and the number of bills in Maxim's wallet.

The second line of the input contains nn integers c1,c2,…,cnc_1, c_2, \dots, c_n (1≤ci≤10001 \le c_i \le 1000), where cic_i is the cost of the ii-th game.

The third line of the input contains mm integers a1,a2,…,ama_1, a_2, \dots, a_m (1≤aj≤10001 \le a_j \le 1000), where aja_j is the value of the jj-th bill from the Maxim's wallet.

输入的第一行包含两个整数 nn 和 mm(1≤n,m≤10001 \le n, m \le 1000)——分别表示游戏的数量以及 Maxim 钱包中纸币的数量。

输入的第二行包含 nn 个整数 c1,c2,…,cnc_1, c_2, \dots, c_n(1≤ci≤10001 \le c_i \le 1000),其中 cic_i 表示第 ii 个游戏的价格。

输入的第三行包含 mm 个整数 a1,a2,…,ama_1, a_2, \dots, a_m(1≤aj≤10001 \le a_j \le 1000),其中 aja_j 表示 Maxim 钱包中第 jj 张纸币的面值。

输出格式

Print a single integer — the number of games Maxim will buy.

输出一个整数——Maxim 将购买的游戏数量。

输入输出样例

  • 输入#1

    5 4
    2 4 5 2 4
    5 3 4 6

    输出#1

    3
  • 输入#2

    5 2
    20 40 50 20 40
    19 20

    输出#2

    0
  • 输入#3

    6 4
    4 8 15 16 23 42
    1000 1000 1000 1000

    输出#3

    4

说明/提示

The first example is described in the problem statement.

In the second example Maxim cannot buy any game because the value of the first bill in his wallet is smaller than the cost of any game in the shop.

In the third example the values of the bills in Maxim's wallet are large enough to buy any game he encounter until he runs out of bills in his wallet.

第一个示例已在题目描述中给出。

在第二个示例中,Maxim 无法购买任何游戏,因为其钱包中第一张纸币的面值小于商店中任意一款游戏的价格。

在第三个示例中,Maxim 钱包中纸币的面值足够大,以至于他可以购买所遇到的任意一款游戏,直至钱包中的纸币用尽。

输入解题思路,AI测评打分。不知道怎么写?

首页