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

作者: wjyyy 分类: 快速排序,数据结构,树状数组,模拟,解题报告 发布时间: 2018-06-09 15:42

点击量:26

当时考试看到这个题感觉暴力挺多分的,结果暴力一打并开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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */