当前位置: 首页 > article >正文

第十五届蓝桥杯C/C++B组拔河问题详解

kans

解题思路

这道题目的难点在于枚举所有区间,并且区间不能重合,那么这样感觉就很难了。但是用下面这种方法就会好很多。
在这里插入图片描述

我们只需要将左边的所有区间的各种和放在一个set中,然后我们在枚举右边的所有区间的和去和它进行比较,然后求出差值,如果差值比最小的小,那么就更新答案,那么我们只需要去从左边到右边移动线的位置就行。

代码实现

#include<iostream>
#include<vector>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int N=1e4;
int p[N];
long long sum[N];
typedef long long LL;
set<LL>a;
int main()
{
    ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		sum[i]=sum[i-1]+p[i];//前缀和
	}
    LL res=1e15;
    a.insert(1e15);//防止找不到比右边区间大的左边的
    a.insert(-1e15);//防止找不到比右边区间小的左边的
    for(int i=1;i<=n;i++)//枚举中间的线
    {
        for(int l=1;l<=i-1;l++)//枚举左边的所有区间
        {
            a.insert(sum[i-1]-sum[l-1]);//插入前面的区间[l,i-1];
        }       
        for(int r=i;r<=n;r++)
        {
            LL s=sum[r]-sum[i-1];//枚举右边的所有区间和
            auto it= a.lower_bound(s);//大于这个数的最小数
            res=min(res,(*it-s));
            it--;//找到小于这个数的最大数
            res=min(res,(s-*it));
        }
    }
    cout<<res;
    return 0;
}

http://www.kler.cn/a/587475.html

相关文章:

  • Vision Transformer (ViT):将Transformer带入计算机视觉的革命性尝试(代码实现)
  • 7年全栈开发经验 · 兼职技术合作
  • ShenNiusModularity项目源码学习(16:ShenNius.Admin.Mvc项目分析-1)
  • L1-7 统一命名规范(java)
  • 【ESP32】ESP-IDF开发 | 经典蓝牙开发 | 蓝牙串口协议(SPP) + 客户端和服务端例程
  • MyBatis框架操作数据库一>xml和动态Sql
  • 基于单片机的豆浆机控制系统设计(论文+源码)
  • 软件环境安装-通过Docker安装RocketMQ
  • 安卓实现魔改版 Base64 算法
  • 什么是机器学习?从零基础到自动驾驶案例全解析
  • 阿里FPGA XCKU3P开箱
  • 国内Mac,nimi安装homebrew完整过程
  • Rust从入门到实战
  • 【Go每日一练】实现简单的控制台计算器
  • 简单的bug+1
  • 现代密码学 | 具有保密和认证功能的安全方案
  • 软考网络安全专业
  • 基于大模型预测的难治性青光眼诊疗方案研究报告
  • Leetcode:34(二分查找)
  • Android(java)高版本 DownloadManager 封装工具类,支持 APK 断点续传与自动安装