小埋的解密游戏的题解

目录

原题描述：

题目描述

输入格式

输出格式

样例 #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;
}