首页 > 其他分享 >P10429 [蓝桥杯 2024 省 B] 拔河 题解

P10429 [蓝桥杯 2024 省 B] 拔河 题解

时间:2024-05-08 16:56:02浏览次数:11  
标签:P10429 diffs min 题解 sum range 蓝桥 prefix diff

思路

通过动态规划计算出所有连续子序列的力量值之和,并将其存储在一个数组中然后排序,遍历一遍数组,找到相邻两个力量值之和的差的绝对值的最小值,然后输出这个答案就行了。

时间复杂度大概是 \(O(n^2 \log n)\)。

来个 python 的代码

def min_power_diff(n, a):# 计算所有连续子序列的力量值之和
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + a[i - 1]
    # 计算差值并排序
    diffs = []
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            diff = abs(prefix_sum[j] - prefix_sum[i - 1])
            diffs.append(diff)
    diffs.sort()
    # 找到相邻两个力量值之和的差的最小值
    min_diff = float('inf')
    for i in range(1, len(diffs)):
        min_diff = min(min_diff, diffs[i] - diffs[i - 1])
    return min_diff
n = int(input())
a = list(map(int, input().split()))
# 输出答案
result = min_power_diff(n, a)
print(result)

标签:P10429,diffs,min,题解,sum,range,蓝桥,prefix,diff
From: https://www.cnblogs.com/BadBadBad/p/18180225/P10429

相关文章

  • 「高精度乘法+高精度加法」P10425 [蓝桥杯 2024 省 B] R 格式 题解
    解题思路题意分析:将浮点数乘以\(2^n\);四舍五入到最接近的整数。根据题意将\(d\times2^n\)分解为\(d\times2\times2\times2\times2……\),因为\(d\)长度小于等于\(1024\),所以可以使用高精度乘法的算法来实现一个小数乘以一个大于\(0\)的整数时,小数点位数本身不会......
  • P8754 [蓝桥杯 2021 省 AB2] 完全平方数
    原题链接题解分解n的质因子,如果为奇数就补一个由于大于\(\sqrt{n}\)的质因子最多不超过一个,所以我们筛小于\(1e6\)的质数code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;vector<int>prime;vector<int>minfac(1e6+3,0);intmain(){f......
  • 蓝桥杯-蚂蚁感冒
    长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左,有的朝右。每只蚂蚁都只能沿着杆子向前爬,速度是1厘米/秒。当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行。这些蚂蚁中,有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时,会把感冒传染给碰到的蚂蚁。请你计算,当所有蚂蚁......
  • [COCI2022-2023#1] Berilij 题解
    SolutionP9030[COCI2022-2023#1]Berilij本题解转载翻译自官方题解:COCI2022/2023CONTEST1Part1让我们定义图形\(G\),顶点代表飞船,边代表两艘飞船外部接触的情况。此外,让边的边权成为它所连接的圆之间的距离。现在的任务等同于为顶点找到非负值,使得每条边所连接的两个顶......
  • 蓝桥杯-买不到的数目
    小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候,他就用这两种包装来组合。当然有些糖果数目是无法组合出来的,比如要买10颗糖。你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。大于17的任何数字......
  • cuda使用时Could not locate zlibwapi.dll 问题解释和解决
    第一次配置cuda环境,python环境训练模型时,可能遇到Couldnotlocatezlibwapi.dll.Pleasemakesureitisinyourlibrarypath! 原因就是window系统里没有zlibwapi.dll.,与cuda没关系,cuda只是依赖它。安装某些软件时可能会自动把这个动态库安装到系统的某个path路径下,比如......
  • ICPC2024 武汉邀请赛 题解
    2024ICPCNationalInvitationalCollegiateProgrammingContest,WuhanSiteB-CountlessMeSolution显然,只能执行\(n\)次操作是没用的条件我们只需要把和\(sum\)分给\(n\)个数,使得\(n\)个数的或和最小即可从高到低考虑每一位,假设此时枚举到第\(i\)位如果这一......
  • 蓝桥杯国赛训练第一周
    P1491集合位置-洛谷|计算机科学教育新生态(luogu.com.cn)主要在于$A*$函数中估价函数,这里给出最好想也是我想出来的一种方法,也就是当黑白棋子各自都在对方的领域上,那么就可以考虑一种最小的消耗情况,也就是走一步顶两不,也就是黑白互换,那么此时所需要消耗的最小步数......
  • 【题解】爬山 蓝桥杯2024省B
    题目链接:P10429[蓝桥杯2024省B]拔河[蓝桥杯2024省B]拔河题目描述小明是学校里的一名老师,他带的班级共有\(n\)名同学,第\(i\)名同学力量值为\(a_i\)。在闲暇之余,小明决定在班级里组织一场拔河比赛。为了保证比赛的双方实力尽可能相近,需要在这\(n\)名同学中挑选......
  • 蓝桥杯-翻硬币
    小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用*表示正面,用o表示反面(是小写字母,不是零)。比如,可能情形是:**oo***oooo如果同时翻转左边的两个硬币,则变为:oooo***oooo现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个......