洛谷 P2345 奶牛集会 题解【暴力】【树状数组】【逆序对】【排序】

点击量：311

当时考试看到这个题感觉暴力挺多分的，结果暴力一打并开O2就A了？？？数据略水。。。

目录

题目背景

MooFest, 2004 Open

题目描述

约翰的\(N\)头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第\(i\)头奶牛的坐标为\(X_i\)，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第\(i\)头和第\(j\)头奶牛交流，会发出\(\max(V_i,V_j)\times |X_i-X_j|\)的音量，其中\(V_i\)和\(V_j\)分别是第\(i\)头和第\(j\)头奶牛的听力。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

输入输出格式

输入格式：

• 第一行：单个整数\(N,1\le N\le 20000\)

• 第二行到\(N+1\)行：第\(i+1\)行有两个整数\(V_i\)和\(X_i\)，\(1\le V_i\le 20000,1\le X_i\le 20000\)

输出格式：

• 单个整数：表示所有奶牛产生的音量之和

输入输出样例

输入样例#1：

4
3 1
2 5
2 6
4 3

输出样例#1：

57

暴力代码：（禁止模仿

// luogu-judger-enable-o2
#include<cstdio>
int abs(int x)
{
    if(x<0)
        return -x;
    return x;
}
int max(int x,int y){return x>y?x:y;}
struct cow
{
    int v,x;
}c[20050];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&c[i].v,&c[i].x);
    long long sum=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            sum+=abs(c[i].x-c[j].x)*max(c[i].v,c[j].v);
    printf("%lld\n",sum);
    return 0;
}

切入正题：

    树状数组求逆序对的思想和开车旅行倒序插入的思想，将声音较小的奶牛先插入，这样可以避免使用max，因为当前插入的一定是声音最大的，我们只需要分别统计在当前坐标左边的、右边的牛的坐标和以及个数，用个数乘上当前坐标减去左边的坐标和，加上右边坐标减去个数乘上当前坐标。

     维护左边和右边坐标和，需要用树状数组维护。

     再用它们的坐标差之和乘上它们所产生的音量，就是答案了。-记得开long long。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using std::pair;

bool flag[20080];
struct node
{
    int x1,x2,x3;//x1是声音大小，x3是位置
    friend bool operator <(node x,node y)
    {
        if(x.x1!=y.x1)
            return x.x1<y.x1;
        if(x.x2!=y.x2)
            return x.x2<y.x2;
        return x.x3<y.x3;
    }
}a[20080];
pair<int,long long> c[20080];
bool cmp(node x,node y)
{
    return x.x3<y.x3;
}
int n;
int lowbit(int x)
{
    return x&(-x);
}
void add(int t,int x,long long y)
{
    while(t<=n)
    {
        c[t].first+=x;
        c[t].second+=y;
        t+=lowbit(t);
    }
    return;
}
int ask(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x].first;
        x-=lowbit(x);
    }
    return sum;
}
long long ask2(int x)
{
    long long sum=0;
    while(x>0)
    {
        sum+=c[x].second;
        x-=lowbit(x);
    }
    return sum;
}
int X[20080];
int main()
{
    memset(flag,0,sizeof(flag));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].x3,&a[i].x1);
        a[i].x2=i;//离散化的坐标
    }
    std::sort(a+1,a+1+n);
    a[0].x1=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].x1==a[i-1].x1)
            flag[i]=true;
        X[i]=a[i].x1;
    }
    for(int i=1;i<=n;i++)
        if(flag[i])
            a[i].x1=a[i-1].x1;
        else
            a[i].x1=i;

    std::sort(a+1,a+1+n,cmp);

    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        add(a[i].x1,1,X[a[i].x1]);
        sum+=a[i].x3*(ask(a[i].x1-1)*X[a[i].x1]-ask2(a[i].x1-1));
        sum+=a[i].x3*((ask2(n)-ask2(a[i].x1))-(ask(n)-ask(a[i].x1))*X[a[i].x1]);
    }
    printf("%lld\n",sum);
    return 0;
}