首页 > 代码库 > P2345 奶牛集会andP2657 低头一族

P2345 奶牛集会andP2657 低头一族

做法是一样的

技术分享
题目背景

MooFest, 2004 Open

题目描述

约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很

多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i 头奶牛的坐标为Xi,没有两头奶牛的坐标是相同的。奶牛们的叫声很大,第i 头和第j 头奶牛交流,会发出max{Vi; Vj}×|Xi ? Xj | 的音量,其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。假设每对奶牛之间同时都在说话,请计算所有奶牛产生的音量之和是多少。

输入输出格式

输入格式:
? 第一行:单个整数N,1 ≤ N ≤ 20000

? 第二行到第N + 1 行:第i + 1 行有两个整数Vi 和Xi,1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000

输出格式:
? 单个整数:表示所有奶牛产生的音量之和

输入输出样例

输入样例#14
3 1
2 5
2 6
4 3
输出样例#157
说明

朴素O(N2)

类似于归并排序的二分O(N logN)

树状数组O(N logN)
V奶牛的集会
技术分享
题目描述

一群青年人排成一队,用手机互相聊天。

每个人的手机有一个信号接收指标,第i个人的接收指标设为v[i]。

如果位置在x[i]的人要和位置在xj的人聊天,那么这两人组成的一对的信号发射强度就是abs(x[i]-x[j])*max(v[i],v[j]).

现在我们想知道,这些人所有对子中的信号发射强度的总和。

输入输出格式

输入格式:
第一行一个整数N,接下来N行,每行两个整数v[i]和x[i]。

输出格式:
所有对的信号发射强度总和。

输入输出样例

输入样例#14
3 1
2 5
2 6
4 3
输出样例#157
说明

对于40%的数据,N<=5,000

对于100%的数据,N<=100,000 1≤x[i]≤20,000

[color=red]注意:可能有两人在同一个位置
答案在int64或long long范围内[/color]
低头一族

 思路: 

  先按照V排一下序只考虑X就行了,因为对于V大的来说,他和别人的贡献只是X的差得和。(这个用lowbit维护)。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<cmath>
using namespace std;
typedef long long LL; 
int n;
LL num[20010],tot[20010];
struct node{
    int x;
    int v;
}a[100009];
int lowbit(int x)    {return x&(-x);}
bool cmp(node  a,node  b)
{
    return a.v<b.v;
}
long long ans;
int MAX;
void Add(LL *C,int x,int y)
{
    while(x<=MAX)
    {
        C[x]+=y;
        x+=lowbit(x);
    }
}
LL query(LL *C,int x)
{
    LL res=0;
    while(x>0)
    {
        res+=C[x];
        x-=lowbit(x);
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].v,&a[i].x),MAX=max(MAX,a[i].x);
    sort(a+1,a+1+n,cmp);
    for(int i=1,x,v;i<=n;i++)
    {
        x=a[i].x,v=a[i].v;
        LL totl,totr,numl,numr;
        numl=query(num,x-1);totl=query(tot,x-1);
        numr=query(num,MAX)-query(num,x);totr=query(tot,MAX)-query(tot,x);
        
        ans+=v*(totr-totl+x*numl-x*numr);
        Add(num,x,1);
        Add(tot,x,x);
    }
    cout<<ans;
    return 0;
}

 

P2345 奶牛集会andP2657 低头一族