网站开发面板聊城高新区建设局网站
目录
原题描述：
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
提示
主要思路：
代码实现code：
原题描述：
题目描述
小埋最近在玩一个解密游戏，这个游戏的解密方法是这样的，这个游戏会给你提供 个数,让我们求出这
个数里面，有多少个连续的数的平均数大于某个给定的数
。这个数可能会很大，所以我们要输出这个数对
的取模结果。现在小埋对于这个游戏的解法还是不太理解，现在请你帮助小埋解决这个问题。
输入格式
输入有两行。第一行为两个数 和
。第二行为
个数。
输出格式
输出的数占一行，即问题的解对 取模的结果。
样例 #1
样例输入 #1
4 3
1 5 4 2样例输出 #1
5样例 #2
样例输入 #2
4 4 5 2 7 3样例输出 #2
6提示
所有的数均为正整数且不大于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;
}