360笔试算法题 20240803

1、探险（双指针）

题目描述：

小X在一片大陆上探险，有一天他发现了一个洞穴，洞穴里面有n道门，打开没到门都需要对应的钥匙，编号为i的钥匙能用于打开第i道门，而且只有在打开了第i道门后，才能打开第i+1道门，一开始只能打开第一道门。每天能发现一把钥匙，且每天找到钥匙后，会去打开所有能够打开的门，现在给出他每天找到的钥匙编号，请问每道门分别在哪一天被打开。

输入描述：

第一行包括一个正整数n，表示门的数量。

接下来一行包含n个正整数a1,a2,…,an，其中ai表示第i天他找到的钥匙编号，能够打开第ai道门，数据保证a1-an为1-n的一个排列

输出描述：

输出一行n个数s1,s2,…,sn，其中si表示第i道门在第si天被打开。

样例输入：

5

5 3 1 2 4

样例输出

3 4 4 5 5

for i in range(n):
    have[arr[i]] += 1
    while now <= n and have[now]:
        ans[now] = i + 1
        now += 1

2、骑行（动态规划）

题目描述：

某个公司的共享单车单词骑行1元，但可以购入VIP卡免去骑行费用，有以下几种VIP卡：

日卡a元，1天不收费；

月卡b元，30天不收费；

年卡c元，365天不收费；

十年卡d元，3650天不收费。

每天都允许购入任意张VIP卡，生效时间可累加。

小A在未来n天都需要骑共享单车，第i天需要骑行ri次，现在小A想知道，他最少以要花多少钱。

输入描述：

第一行一正整数n(1<=n<=10^5)

第二行四个正整数a,b,c,d(1<=a,b,c,d<=10^7)，表示四种卡的价格。

第三行n个正整数ri(1<=ri<=10^9)，表示每天骑行次数

输出描述：

输出一个整数x，表示最小花费。

样例输入：

10

2 40 400 3000

1 4 2 4 2 2 1 1 100 1

样例输出：

16

dp[i] = dp[i-1] + prices (不买卡)
dp[i] = min(dp[i], dp[i-1] + a) (买日卡)
dp[i] = min(dp[i], dp[max(0, i-30)] + b) (买月卡)
dp[i] = min(dp[i], dp[max(0, i-365)] + c) (买年卡)
dp[i] = min(dp[i], dp[max(0, i-3650)] + d) (买十年卡)