中值数问题,均分纸牌问题模板
作者:
开心小子
,
2019-08-27 21:45:25
,
所有人可见
,
阅读 992
//中值数问题,均分纸牌问题模板
#define ll long long
#define pii pair<bool ,ll >
int s1[maxn];
pii fun(int a[],int num) //a[]表示要均分纸牌的数组,num表示数组的范围
{ memset(s1,0,sizeof(s1));//对每次均分纸牌问题的数组都要进行归零重置
ll sum=0;
for(int i=1;i<=num;i++)
sum+=a[i];
if(sum%num!=0)
{ //当该问题不能均分时返回假
return make_pair(false, 0);
}
sum/=num;
for(int i=2;i<=num;i++)
{
s1[i]+=s1[i-1]-sum+a[i];
}
sort(s1+1,s1+1+num);
ll tar=0;
for(int i=1;i<=num;i++)
{
tar+=abs(s1[i]-s1[num/2+1]);//这里取中值数为 num/2+1的原因是防止当num=1去访问0位置
}
return make_pair(true,tar);
}