首页 > 试题广场 >

射击训练

[编程题]射击训练

热度指数：1544 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小Q 是一个专业的射击运动员，有一天他像往常一样进行 n 次射击训练，每次射击他都会取最高的四次得分作为最终得分来衡量他的射击状态，但是今天他制定了一个奇怪的规则：在 n 次射击得分中取出四次得分 a,b,c,d ，并且满足 a*b*c=d 作为最终得分来衡量他的射击状态。

但是小Q 发现满足这个条件的 (a,b,c,d) 可能不止一个，小Q 需要你来帮助他计算一共有多少个这种 (a,b,c,d)

数据范围： $4 \le n \le 500 \$ ，输入的所有得分满足 $1 \le w_i \le 1000 \$

输入描述:

输入包括两行，第一行包括一个正整数n，表示射击的次数。

第二行n个正整数，表示每次射击的得分。

输出描述:

输出可以作为最终得分的种数。

示例1

输入

6
10 2 2 7 40 160

输出

说明

有两种满足条件的(a,b,c,d)分别是(10,2,2,40)和(2,2,40,160)。

算法知识视频讲解

Python 3

牛客645538045号

Test cases are incorrect, no zero elements are allowed.

I have tested some datas and are proved to be "correct".

import sys
number = eval(input())
num_list = []
lst = input()
for i in lst.split():
    num_list.append(eval(i))
    
num_list.sort()
def fullfill(a, b, c, d) :
    if (a==b):
        return fullfill(a, b+1, c, d)
    if (b==c):
        return fullfill(a, b, c+1, d)
    if (c==d):
        return fullfill(a, b, c, d+1)
    if d>=number:
        return 0
    product = num_list[a]*num_list[b]*num_list[c]
    if product < num_list[d]:
        return fullfill(a, b, c, d+1)
    else:
        return (product == num_list[d]) + max(fullfill(a, b+1, c, d), fullfill(a, b, c+1, d), fullfill(a+1, b, c, d))

print(fullfill(0, 1, 2, 3))

This code used a sorting function, which costs O(nlogn) time, simply moving the window should give O(n) amount of time. Therefore, the overall runtime should be O(nlogn)

发表于 2022-03-23 03:01:14 回复(0)