USACO26 moofest 奶牛集会（归并排序）

听说这题也是bzoj的3378&&poj1990，然而没有权限号交不了。。poj懒得登。

题意：有n个奶牛，他们相互发出max(a[i].v,a[j].v)*abs(a[i].p-a[j].p)的声音，求这个的和。

绝望，刷这题的时候本来傻逼想%题解的，结果网上的都是树状数组，唯一找到的一个归并排序还TMD是错的。。吃鲸，没办法，只好自己做。

不难发现（如果你%过其他题解），这里v要的是最大值，那我们就用大的将比他小的全部乘起来，那具体在归并排序里面怎么实现呢，我们先按位置从大到小快排，然后大到小归并排序v的大小（这两个排序反过来也行，不过就要自己推公式了），当a[i].v>a[j].v时，说明j~r所有的v，都要比a[i].v小，那就加上a[i].v*sigema(k=j~r)(a[k].p-a[i].p)，同理当a[i].v<a[j].v时，a[i].v*sigema(k=i~mid)(a[i].p-a[k].p)，a[i].p的个数是确定的，我们只需要预处理一下另外一项就行了。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

struct node

{

    int v,p;

}a[],t[];

bool cmp(node n1,node n2)

{

    if(n1.p>n2.p)return true;

    return false;

}

LL ans;

void mergesort(int l,int r)

{

    if(l==r)return ;

    int mid=(l+r)/;

    mergesort(l,mid);

    mergesort(mid+,r);

    LL suml=,sumr=;

    for(int i=l;i<=mid;i++)suml+=a[i].p;

    for(int i=mid+;i<=r;i++)sumr+=a[i].p;

    int i=l,j=mid+,p=l;

    while(i<=mid&&j<=r)

    {

        if(a[i].v>a[j].v)

        {

            ans+=a[i].v*((r-j+)*a[i].p-sumr);

            suml-=a[i].p;

            t[p++]=a[i++];

        }

        else

        {

            ans+=a[j].v*(suml-(mid-i+)*a[j].p);

            sumr-=a[j].p;

            t[p++]=a[j++];

        }

    }

    while(i<=mid)t[p++]=a[i++];

    while(j<=r)t[p++]=a[j++];

    for(int i=l;i<=r;i++)a[i]=t[i];

}

int main()

{

    freopen("moofest.in","r",stdin);

    freopen("moofest.out","w",stdout);

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d%d",&a[i].v,&a[i].p);

    sort(a+,a+n+,cmp);

    ans=;

    mergesort(,n);

    printf("%lld\n",ans);

    return ;

}

巴特西

USACO26 moofest 奶牛集会（归并排序）

最新文章

热门文章