首页 > 其他分享 >【题解】爬山 蓝桥杯2024省B

【题解】爬山 蓝桥杯2024省B

时间:2024-05-07 12:12:39浏览次数:25  
标签:2024 10 题解 样例 蓝桥 leq 队伍

题目链接:P10429 [蓝桥杯 2024 省 B] 拔河

[蓝桥杯 2024 省 B] 拔河

题目描述

小明是学校里的一名老师,他带的班级共有 \(n\) 名同学,第 \(i\) 名同学力量值为 \(a_i\)。在闲暇之余,小明决定在班级里组织一场拔河比赛。

为了保证比赛的双方实力尽可能相近,需要在这 \(n\) 名同学中挑选出两个队伍,队伍内的同学编号连续 \(\{{a_{l_1}}, a_{l_1 + 1}, \dots, a_{r_1 - 1}, a_{r_1}\}\) 和 \(\{{a_{l_2}}, a_{l_2 + 1}, \dots, a_{r_2 - 1}, a_{r_2}\}\),其中 \(l_1 \le r_1<l_2 \le r_2\)。

两个队伍的人数不必相同,但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输入格式

输入共两行。
第一行为一个正整数 \(n\)。
第二行为 \(n\) 个正整数 \(a_1, a_2, \dots a_n\)。

输出格式

输出共一行,一个非负整数,表示两个队伍力量值之和的最小差距。

样例 #1

样例输入 #1

5
10 9 8 12 14

样例输出 #1

1

提示

样例 1 解释

其中一种最优选择方式:

队伍 1:\(\{a_1, a_2, a_3\}\),队伍 2:\(\{a_4, a_5\}\),力量值和分别为 \(10 + 9 + 8 = 27\),\(12 + 14 = 26\),差距为 \(|27 − 26| = 1\)。

数据规模与约定

  • 对 \(20\%\) 的数据,\(n \leq 50\)。
  • 对全部的测试数据,保证 \(1 \leq n \leq 10^3\),\(1 \leq a_i \leq 10^9\)。

解法:

把所有以i(\(1 \leq i \leq n\))开头的区间暴力出来,进行排序,因为要找最小差值,排序后,相邻的一定是差最小的,所以按每个区间的值从小到大排序,然后对相邻区间取差值找最小差值。

代码:

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int,int>

const int N=1010; 
int n,a[N],s[N],res=1e18;
vector<pii>v;


signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			v.push_back({s[j]-s[i],i});
		}
	}
	
	sort(v.begin(),v.end());
	
	for(int i=0;i<v.size()-1;i++)
	{
		res=min(res,v[i+1].first-v[i].first);
	}
	printf("%lld",res);
	
	return 0;
}

标签:2024,10,题解,样例,蓝桥,leq,队伍
From: https://www.cnblogs.com/watasky/p/18176988

相关文章

  • 《安富莱嵌入式周报》第336期:开源计算器,交流欧姆表,高性能开源BLDC控制器,Matlab2024a,操
    周报汇总地址:http://www.armbbs.cn/forum.php?mod=forumdisplay&fid=12&filter=typeid&typeid=104 本周更新一期视频教程:BSP视频教程第30期:UDSISO14229统一诊断服务CAN总线专题,常用诊断执行流程精讲,干货分享,图文并茂https://www.armbbs.cn/forum.php?mod=viewthread&tid=12......
  • Testing Egineer note:2024_5_7-day06-part01
    设计测试用例方法之术语介绍1.软件测试中术语动态测试(dynamictesting):通过运行软件的组件或系统来测试软件例如:一辆汽车发动并行使测试静态测试(statictesting):对组件的规格说明书进行评审,对静态代码进行走查例如:一辆汽车为发动未行驶,查看外观、颜色、组成部分正式......
  • 【2024-05-01】连岳摘抄
    23:59致所有顶天立地却平凡普通的无名的人啊,我敬你一杯酒,敬你的沉默和每一声怒吼,敬你弯着腰上山往高处走,头顶苍穹努力地生活。                                              ......
  • 远光九天平台入选2024全国企业数字化应用创新典型案例
    4月25日至29日,由科技部、国家发展改革委、工业和信息化部、国务院国资委、中国科学院、中国工程院、中国科协、北京市人民政府共同主办的2024中关村论坛在北京召开。远光软件受邀出席2024中关村论坛平行论坛之一——全球数字化应用创新论坛,其倾力打造的远光九天智能一体化云平台(简......
  • 蓝桥杯-翻硬币
    小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用*表示正面,用o表示反面(是小写字母,不是零)。比如,可能情形是:**oo***oooo如果同时翻转左边的两个硬币,则变为:oooo***oooo现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个......
  • XMOJ 四月月赛 T3 旅行 题解
    我们首先尝试挖掘这个分组的性质。我们发现,我们可以把在同一个组的夫妻和不在同一个组的夫妻分开来处理。这里,分开之后我们只需要让一种情况有顺序,另外一种不能有顺序。如果两个没有顺序/有顺序的序列合并,一定会出现漏算/多算。所以为了方便,我们可以把第二种情况看作有顺......
  • 2024.05 做题笔记
    P6617由于\(w\)是固定的,容易想到去维护前驱。具体而言,对于每个\(i\),维护\(i\)之前第一个\(w-a_i\),这样可以解决不带修的部分分。发现带修就寄了!因为一次可能修改\(\mathcalO(n)\)个位置的前驱。但是考虑到我们只需要判断是否存在,因此如果\(a_i\)前的第一个\(w-a_i\)......
  • 工作感受月记(202405月)
    2024年05月06号新的一月工作天,旧事未清理,新事不停生。今日工作事项:1/来了一个新案例,apimstv1升级到stv2的情况,客户需要noam同学来帮助建会议处理问题。2/自己研究durablefunction的4001端口问题,证明确实是gRPC需要使用,用于isolatedprocess处理时候,进程间通信所用。如果......
  • 2024-05-06 vue获取页面元素高度(注意view标签无法获取到高度,请用div)
    要获取元素高度要满足以下条件:1、组件或页面已加载完毕;2、使用ref绑定的是标准的dom先贴获取方法:用ref绑定元素title,然后在mounted使用this.$refs.title.offsetHeight获取。为什么要满足条件1?因为页面没渲染完成是无法获取到元素的。为什么要满足条件2?如果你是使......
  • 2024.5.6 近期练习
    P3354[IOI2005]Riv河流如果我们设\(f_{u,j}\)表示子树\(u\)内放了\(j\)个伐木场的答案,发现很难转移。我们多加状态,设\(f_{u,i,j}\)表示子树\(u\)放了\(j\)个伐木场,木材全部运到\(i\)去最小代价。\(i\)是\(j\)祖先。继续设\(g_{u,i,j}\)表示\(u\)建了伐......