洛谷 P2717 寒假作业

news/2024/2/28 5:29:37

题目背景

zzs和zzy正在被寒假作业折磨,然而他们有答案可以抄啊。

题目描述

他们共有n项寒假作业。zzy给每项寒假作业都定义了一个疲劳值Ai,表示抄这个作业所要花的精力。zzs现在想要知道,有多少组连续的寒假作业的疲劳值的平均值不小于k?

简单地说,给定n个正整数A1,A2,A3,...,An,求出有多少个连续的子序列的平均值不小于k。

输入输出格式

输入格式:

 

第一行两个正整数,n和k。

第二行到第n+1行,每行一个正整数Ai。

 

输出格式:

 

一个非负整数。

 

输入输出样例

输入样例#1:
3 2
1
2
3
输出样例#1:
4

说明

样例解释:共有6个连续的子序列,分别是(1)、(2)、(3)、(1,2)、(2,3)、(1,2,3),平均值分别为1、2、3、1.5、2.5、2,其中平均值不小于k的共有4个。

对于20%的数据,1<=n<=100;

对于50%的数据,1<=n<=5000;

对于100%的数据,1<=n<=100000;

对于100%的数据,1<=Ai<=10000,1<=k<=10000。

 

解题思路

  先来简化一下题意:给定一个数列a[],求有多少个子序列元素平均值大于等于k。

  遍历所有子区间复杂度最小O(n^2),可用前缀和O(1)得到任意区间和。

  想个办法吧,这类题要么用奇奇怪怪的数据结构(可能有这样的数据结构?我不知道),要么推公式。

  那就推公式——

  首先取出一段区间吧,设1<=i<=j<=n,然后这段区间(a[i]~a[j])的平均值为

    (a[i]+a[i+1]+…+a[j]) / (j-i+1)>=k

    分母不太好看,乘到右边吧——

    a[i]+a[i+1]+…+a[j] >= k*(j-i+1)

    a[i]+a[i+1]+…+a[j]>= k+…+k //(j-i+1)个k

    接下来有点关键啦

    a[i]+a[i+1]+…+a[j] - k-…-k>=0

    (a[i]-k) + (a[i+1]-k) +……+ (a[j]-k)>=0//哦?那么整齐,有意思

    那我们另设一个数组b[],使b[i]=a[i]-k吧

    b[i]+b[i+1]+…+b[j]>=0

    哦?b[]的一段区间和大于等于零?

  记得前面想暴力的时候说过用前缀和能O(1)取得任意区间和吗?给b[]套上区间和吧

  设s[i]=b[1]+b[2]+b[3]+…+b[i],特别的,令s[0]=0,那么b[i]+b[i+1]+…+b[j] = s[j]-s[i-1]。

    s[j] - s[i-1]>=0

    移项一下

    s[j]>=s[i-1],哇,快了。

    因为之前定义过i<=j,所以i-1<j,这是什么?

    是的没错!逆序对(大雾,应该叫顺序对的)!

    i-1<j且s[i-1]<=s[j],对s数组求逆序对顺序对即可。

  不会求逆序对的就先掌握这个姿势吧,也挺简单的。

  最后说一下,我不知道为什么把求逆序对的程序类比着改一下,求出来“顺序对”就是对的,反正套上去就AC了,如果有那个dalao知道,能在评论区为本蒟蒻解惑吗?谢谢了。

源代码

#include<stdio.h>int n,k;
int a[100010]={0},temp[100010]={0};
long long ans=0;void merge(int s1,int e1,int s2,int e2)
{int s=s1,e=e2,i=s1;while(s1<=e1&&s2<=e2){if(a[s1]<=a[s2]){ans+=e2-s2+1;//求逆序对在"a[s1]>a[s2]"里,求顺序对反过来temp[i++]=a[s1++];}elsetemp[i++]=a[s2++];}while(s1<=e1) temp[i++]=a[s1++];while(s2<=e2) temp[i++]=a[s2++];for(i=s;i<=e;i++) a[i]=temp[i];
}
void msort(int l,int r)
{if(l==r) return;int mid=(l+r)>>1;msort(l,mid);msort(mid+1,r);merge(l,mid,mid+1,r);
}int main()
{scanf("%d%d",&n,&k);for(int i=1,b;i<=n;i++){scanf("%d",&b);b-=k;a[i]=a[i-1]+b;//输入a[i]时就顺带处理出了s[i],依然存在a[i]里
    }msort(0,n);printf("%lld",ans);return 0;
}

 


http://www.ppmy.cn/news/207479.html

相关文章

洛谷P2717 寒假作业(cdq分治+归并排序求逆序数)

2020.6.13 君子做事得有担当&#xff0c;这个题目我确实不太明白什么意思&#xff0c;只会O(N^2)的朴素解法&#xff0c;看了下题解才发现有逆序数的弟弟顺序数&#xff0c;用归并就过了&#xff1f;&#xff1f; 先去打cf div2&#xff0c;等会再来研究 代码&#xff1a; #i…

洛谷 P2717 寒假作业

题目背景 zzs和zzy正在被寒假作业折磨&#xff0c;然而他们有答案可以抄啊。 题目描述 他们共有n项寒假作业。zzy给每项寒假作业都定义了一个疲劳值Ai&#xff0c;表示抄这个作业所要花的精力。zzs现在想要知道&#xff0c;有多少组连续的寒假作业的疲劳值的平均值不小于k&…

17_Linux根文件简介与Busybox构建文件系统

目录 根文件系统简介 文件目录简介 BusyBox简介 编译BusyBox构建根文件系统 修改Makefile添加编译器 busybox中文字符支持 配置 busybox 编译busybox 向根文件系统添加lib库 向rootfs的“usr/lib”目录添加库文件 创建其他文件夹 根文件系统初步测试 根文件系统简介…

RTD2556T便携式显示器定制!

市场上便携式显示器一般是mstar和瑞昱RTD2556T,但是一般以RTD2556T为主&#xff0c;我司RTD2556T便携式显示器方案已经在大量出货&#xff0c;欢迎同行着我们定制开发!联系人方生 18138859646&#xff08;微信同号&#xff09;

显示器参数--色准

色准就是在色域范围内&#xff0c;显示器显示颜色的准确度&#xff0c;用△E来表示。 假设显示器某像素点需要显示紫色RGB&#xff08;128&#xff0c;0&#xff0c;128&#xff09;&#xff0c;电脑将该像素点的RGB信息输入给显示器&#xff0c;显示器也按照此信息输出紫色了…

外接显示器竖屏

1.在显示里面点击2 切换到外接显示器 2.显示方向改为纵向

在线检测显示器屏幕尺寸

1、我们在桌面新建一个文本文档,并且打开。 2、 在文档里添加以下HTML代码。 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www…

立创梁山派GD32F450ZGT6--移植4针0.96寸OLED显示屏

使用中景园的0.96寸OLED屏代码移植。 以下为该文章使用的屏幕&#xff1a; 开始移植 1、时序问题 首先&#xff0c;因为屏幕的IIC时序需要有微秒的延时&#xff0c;而GD32的库函数自带了毫秒级的滴答定时器。这里需要将毫秒级的滴答定时器&#xff0c;修改为微秒的滴答定时器…

笔记本120赫兹输出html,120Hz显示器vs.60Hz显示器盲测

本文约1248字&#xff0c;需2分钟阅读(全文浏览) 从CRT时代走过来的玩家对刷新率都会有深刻的体会&#xff0c;85Hz以上才会保证屏幕不闪烁。LCD时代刷新率不再是问题&#xff0c;60Hz成为万年标准&#xff0c;不过近年来120Hz甚至144Hz显示器也开始出现&#xff0c;虽然总数量…

LCD12864点阵型液晶显示器介绍

LCD12864点阵型液晶显示器介绍 前言一、LCD12864点阵型液晶显示器介绍1、DDRAM(Data Display Ram)2、CGROM(Character Generation ROM)3、CGRAM(Character Generation RAM)4、GDRAM(Graphic Display RAM)5、HCGROM(Half height Character Generation ROM)6、LCD12864…

京东方GV101WXM-N81-D850参考规格 10.1寸工业液晶屏

GV101WXM-N81-D850 是京东方 (BOE)推出的一款10.1英寸a-Si TFT-LCD液晶模组产品&#xff0c;它装配有WLED背光&#xff0c;含LED驱动器背光驱动&#xff0c;无触摸。 京东方GV101WXM-N81-D850 10.1寸工业液晶屏 应用详情基本信息面板品牌京东方&#xff08;BOE&#xff09;面板…

液晶显示器亮一会(几秒钟)后黑屏【维修笔记】

操作环境(红色粗字体字为修改后内容&#xff0c;蓝色粗体字为特别注意内容)1&#xff0c;显示器&#xff1a;方正显示器&#xff08;液晶&#xff09; 2&#xff0c;参考文献&#xff1a;①https://zhidao.baidu.com/question/1434829226418985499.html②https://wenku.baidu.c…

京东方GV101WXM-N81-D850镜面LED液晶模组 10.1寸工业液晶屏

GV101WXM-N81-D850 是京东方 (BOE)推出的一款10.1英寸a-Si TFT-LCD液晶模组产品&#xff0c;它装配有WLED背光&#xff0c;含LED驱动器背光驱动&#xff0c;无触摸。 京东方GV101WXM-N81-D850 10.1寸工业液晶屏 应用详情基本信息面板品牌京东方&#xff08;BOE&#xff09;面…

京东方GT070WVM-N10-3GP0工业液晶屏 京东方7寸液晶屏供应商

京东方GT070WVM-N10-3GP0工业液晶屏 应用详情基本信息面板品牌京东方&#xff08;BOE&#xff09;面板型号GT070WVM-N10-3GP0面板尺寸7.0英寸面板应用工业面板类型 a-Si TFT-LCD , 液晶模组 存储温度-30 ~ 80 C工作温度-20 ~ 70 C耐振动性京东方GT070WVM-N10-3GP0工业液晶屏 结…

显示器校正

注意事项&#xff1a; 1、显示器校准的环境应注意&#xff1a;防止外来强烈光线进入室内尤其室外强光&#xff1b; 2、工作环境的物体&#xff0c;例如墙、地板、桌面等等要接近中性灰&#xff0c;防止环境影响视觉的判断&#xff1b; 3、显示器要使用遮光罩&#xff0c;防止…

数据结构与算法之美 | 队列(Queue)

对列的相关概念 先进先出&#xff0c;即队列队列的两个基本操作&#xff1a;入队&#xff08;放一个数据到队列尾部&#xff09;和出队&#xff08;从队列头部取一个元素&#xff09;队列是一种操作受限的线性表数据结构 顺序队列和链式队列 用数组实现的队列叫作顺序队列 …

【云原生docker】

容器化越来越受欢迎&#xff0c;因为容器是&#xff1a; ●灵活&#xff1a;即使是最复杂的应用也可以集装箱化。 ●轻量级&#xff1a;容器利用并共享主机内核。 ●可互换&#xff1a;可以即时部署更新和升级。 ●便携式&#xff1a;可以在本地构建&#xff0c;部署到云&#…

差分驱动芯片AM26LS31使用总结

&#xfeff;&#xfeff; http://www.360doc.com/content/16/0808/12/27708084_581651876.shtml 输出电压在3.3V附近&#xff0c;不能达到5V&#xff0c;如果要想达到5V&#xff0c;需要外接上拉电阻。 推荐使用SN75174&#xff0c;SN75172. SN75174 单端转差分&#xff0c;SN…

06 linux 命令 echo -e 参数详解 以及示例;echo输出带颜色

语法 echo [选项] [字符串] echo [-ne][字符串] echo [--help][--version]参数 -n : 输出不换行&#xff08;相当于java的 print&#xff09; -e : 支持反斜杠\ 控制的字符转换控制字符作用\输出 反斜杠 \ 本身\a输出警告省\b退格键[Backspace] 向左删除一个字符\c取消输出行…
最新文章