首页 > 编程语言 > 详细

USACO moofest (归并排序)

时间:2017-10-18 09:46:44      阅读:225      评论:0      收藏:0      [点我收藏+]

听说这题也是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[21000],t[21000];
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)/2;
    mergesort(l,mid);
    mergesort(mid+1,r);
    
    LL suml=0,sumr=0;
    for(int i=l;i<=mid;i++)suml+=a[i].p;
    for(int i=mid+1;i<=r;i++)sumr+=a[i].p;
    
    int i=l,j=mid+1,p=l;    
    while(i<=mid&&j<=r)
    {
        if(a[i].v>a[j].v)
        {
            ans+=a[i].v*((r-j+1)*a[i].p-sumr);
            suml-=a[i].p;
            t[p++]=a[i++];
        }
        else 
        {
            ans+=a[j].v*(suml-(mid-i+1)*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=1;i<=n;i++)scanf("%d%d",&a[i].v,&a[i].p);
    sort(a+1,a+n+1,cmp);
    
    ans=0;
    mergesort(1,n);
    printf("%lld\n",ans);
    return 0;
}

 

USACO moofest (归并排序)

原文:http://www.cnblogs.com/AKCqhzdy/p/7684961.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!