小埋的解密游戏的题解

题目描述

小埋最近在玩一个解密游戏,这个游戏的解密方法是这样的,这个游戏会给你提供 n 个数,让我们求出这 n 个数里面,有多少个连续的数的平均数大于某个给定的数 M 。这个数可能会很大,所以我们要输出这个数对 1e9+7的取模结果。现在小埋对于这个游戏的解法还是不太理解,现在请你帮助小埋解决这个问题。

输入格式

输入有两行。第一行为两个数 n和 M 。第二行为n 个数。

输出格式

输出的数占一行,即问题的解对 1e9+7 取模的结果。

样例 #1

样例输入 #1

4 3 
1 5 4 2

样例输出 #1

5

样例 #2

样例输入 #2

4 4 5 2 7 3

样例输出 #2

6

提示

1 \le n \le 2 * 10^5

1 \le M \le 3*10^3

所有的数均为正整数且不大于5000

主要思路:

这个题目。由于是平均数>m,所以我们可以将所有的数-m,求一遍前缀和,进行归并排序,求出所有的正序对(i<j,且a[i]<a[j])的数对。

代码实现code:

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int a[200010],b[200010];
long long ret=0;
int shu[200010];
void merge(int l,int r)
{
	if(l == r)
	{
		return;
	}
	int mid=(l+r)/2;
	merge(l,mid);
	merge(mid+1,r);//归并排序分治
	int i=l,j=mid+1,tot=l;
	while(i<=mid&&j<=r)
	{
		if(a[i]<a[j])
		{
			ret+=(mid-i+1)%mod;
			ret%=mod;
			b[tot++]=a[j++];	
		}
		else
		{
			b[tot++]=a[i++];
		}
	}
	while(i<=mid)
	{
		b[tot++]=a[i++];	
	}
	while(j<=r)
	{
		b[tot++]=a[j++];
	}//区间合并
	for(int i=l;i<=r;i++)
	{
		a[i]=b[i];
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>shu[i];
		shu[i]-=m;
		a[i] = a[i-1]+shu[i];
	}
	merge(0,n);
	cout<<ret;
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/370781.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

珠海盈致MES系统的应用领域

珠海盈致MES系统在多个领域都有应用&#xff0c;以下是一些主要的应用领域&#xff1a; 注塑行业&#xff1a;针对注塑行业的生产特点和要求&#xff0c;MES系统提供了一系列专业的管理功能&#xff0c;满足注塑企业各种实际生产需求。 电子制造&#xff1a;在电子制造领域&…

算法复杂度之大O复杂度表示法及空间复杂度

目录 简介 时间复杂度 大O复杂度表示法 空间复杂度 前言-与正文无关 生活远不止眼前的苦劳与奔波&#xff0c;它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中&#xff0c;我们往往容易陷入工作的漩涡&#xff0c;忘记了停下脚步&#xff0c;感受周围…

EasyX图形库学习(一、窗口创建函数initgraph、背景颜色设置setbkcolor、图形绘制函数)

目录 一、easyX图形库基本介绍 1、easyX的原理 2、easyX的安装 3、easyX的颜色&#xff08;RGB颜色模型&#xff09; 颜色模型相关函数: 4、easyX的坐标 二、相关函数介绍: 绘图设备相关函数&#xff1a; 图形颜色及样式设置相关函数: 图形绘制相关函数: 文字输出相关…

【Springcloud篇】学习笔记十一(十八章):Seata解决分布式事务问题

第十八章_Seata解决分布式事务问题 1.Seata简介 1.1分布式事务问题由来 分布式前 单机单库没这个问题从1:1 -> 1:N -> N:N 单体应用被拆分成微服务应用&#xff0c;原来的三个模块被拆分成三个独立的应用,分别使用三个独立的数据源&#xff0c;业务操作需要调用三个…

ref和reactive, toRefs的使用

看尤雨溪说&#xff1a;为什么Vue3 中应该使用 Ref 而不是 Reactive&#xff1f; toRefs import { ref, toRefs } from vue;// 定义一个响应式对象 const state ref({count: 0,name: Vue });// 使用toRefs转换为响应式引用对象 const reactiveState toRefs(state);// 现在你…

BUG:docker启动之后直接退出问题

示例如下&#xff1a; 问题排查&#xff1a; 启动命令 sudo docker run --privilegedtrue --runtimenvidia --shm-size80g -v /mmm_data_center:/mmm_data_center -v /imagecenter_new/:/imagecenter_new -v /data1:/data1 -v /mnt/offline_data/:/mnt/offline_data/ --neth…

python 基础知识点(蓝桥杯python科目个人复习计划32)

今日复习内容&#xff1a;基础算法中的位运算 1.简介 位运算就是对二进制进行操作的运算方式&#xff0c;分为与运算&#xff0c;或运算&#xff0c;异或运算&#xff0c;取反&#xff0c;左移和右移。 &#xff08;1&#xff09;与运算 xyx&y000010100111 (2)或运算 …

UE5动画源码剖析

重点剖析的类&#xff1a; UAnimationInstanceFAnimInstanceProxy 参考&#xff1a;https://zhuanlan.zhihu.com/p/405437842 参考&#xff1a;https://blog.csdn.net/qq_23030843/article/details/109103433 参考&#xff1a;https://ikrima.dev/ue4guide/gameplay-programm…

vue实现带缩略图的轮播图(vue-awesome-swiper)

demo 请复制打开 https://download.lllomh.com/cliect/#/product/E125504451206525 如点击链接跳转失败请复制网址到浏览器打开 1.引入swiper和vue-awesome-swiper插件 npm install swiper4 --save npm install vue-awesome-swiper3 --save2.在main.js中引入&#xff1a; …

vue插槽

1.插槽使用 正常渲染子组件时&#xff0c;如果子组件的起始标签和闭合标签内有内容&#xff0c;内容是无法被渲染出来的&#xff0c;如下图&#xff1a; // Son.vue <template><div>子组件</div> </template>// Parent.vue<Son>123123123</S…

vue3 之 项目创建

1.使用create-vue创建项目 前提环境条件 已安装 16.0 或更高版本的 Node.js 创建一个Vue应用 npm init vuelatest 这一指令将会安装并执行 create-vue 2.熟悉项目目录和关键文件

【数据结构与算法】(5)基础数据结构之队列 链表实现、环形数组实现详细代码示例讲解

目录 2.4 队列1) 概述2) 链表实现3) 环形数组实现 2.4 队列 1) 概述 计算机科学中&#xff0c;queue 是以顺序的方式维护的一组数据集合&#xff0c;在一端添加数据&#xff0c;从另一端移除数据。习惯来说&#xff0c;添加的一端称为尾&#xff0c;移除的一端称为头&#xf…

STM32学习笔记(五) —— 按键翻转LED

前面我们分析过GPIO的各个寄存器&#xff0c;探讨了如何使用GPIO点亮LED&#xff0c;这里再验证一下GPIO的输入功能 1.硬件连接 我们在开发板上将按键连接到了PA0引脚&#xff0c;按键外接了上拉电阻&#xff0c;默认状态下PA0引脚处于高电平&#xff0c;当按键按下&#xff0…

七月论文审稿GPT第2.5版:微调GPT3.5 turbo 16K和llama2 13B以扩大对GPT4的优势

前言 我司自去年7月份成立大模型项目团队以来&#xff0c;至今已有5个项目组&#xff0c;其中 第一个项目组的AIGC模特生成系统已经上线在七月官网第二项目组的论文审稿GPT则将在今年3 4月份对外上线发布第三项目组的RAG知识库问答第1版则在春节之前已就绪至于第四、第五项目…

【stm32】hal库学习笔记-ADC模数转换(超详细!)

【stm32】hal库学习笔记-ADC模数转换&#xff08;超详细&#xff01;&#xff09; 本篇章介绍了ADC实现电压检测的三种方式 ADC原理及选型 ADC将连续的模拟电压信号转换为二进制的数字信号 选型参数 速度&#xff08;采样频率&#xff09; 功耗 精度 转换原理 ADC hal库驱…

一、Redis之NoSQL

1.1 什么是NoSQL NoSQL&#xff08;Not Only SQL&#xff09;即不仅仅是SQL&#xff0c;泛指非关系型的数据库&#xff0c;它可以作为关系型数据库的良好补充。随着互联网web2.0网站的兴起&#xff0c;非关系型的数据库现在成了一个极其热门的新领域&#xff0c;非关系数据库产…

[Linux 进程控制(二)] 写时拷贝 - 进程终止

文章目录 1、写时拷贝2、进程终止2.1 进程退出场景2.1.1 退出码2.1.2 错误码错误码 vs 退出码2.1.3 代码异常终止引入 2.2 进程常见退出方法2.2.1 exit函数2.2.2 _exit函数 本片我们主要来讲进程控制&#xff0c;讲之前我们先把写时拷贝理清&#xff0c;然后再开始讲进程控制。…

图论练习2

内容&#xff1a;路径计数DP&#xff0c;差分约束 最短路计数 题目大意 给一个个点条边的无向无权图&#xff0c;问从出发到其他每个点的最短路有多少条有自环和重边&#xff0c;对答案 解题思路 设边权为1&#xff0c;跑最短路 表示的路径数自环和重边不影…

基于OpenCV灰度图像转GCode的双向扫描实现

基于OpenCV灰度图像转GCode的双向扫描实现 引言激光雕刻简介OpenCV简介实现步骤 1.导入必要的库2. 读取灰度图像3. 图像预处理4. 生成GCode 1. 简化版的双向扫描2. 优化版的双向扫描 5. 保存生成的GCode6. 灰度图像双向扫描代码示例 总结 系列文章 ⭐深入理解G0和G1指令&…

【深入浅出Java性能调优】「底层技术原理体系」详细分析探索Java服务器性能监控Metrics框架的实现原理分析(Dropwizard度量基础案例指南)

深入探索Java服务器性能监控Metrics框架的实现原理分析 前提介绍Dropwizard MetricsDropwizard的特点Dropwizard的开发案例需要引入Maven依赖常用度量类型Meter(每秒请求数为单位测量请求率)定义度量核心MetricRegistry构建对应的Meter指标对象请求标记采样业务方法控制报告器…