xml地图|网站地图|网站标签 [设为首页] [加入收藏]

奶牛集会

来源:http://www.ccidsi.com 作者:集成经验 人气:200 发布时间:2019-09-25
摘要:输入输出格式 输入格式:   • 第一行:单个整数N,1 ≤ N ≤ 30000 • 第二行到第N 1 行:第i 1 行有七个整数Vi 和Xi,1 ≤ Vi ≤ 30000; 1 ≤Xi ≤ 三千0   输出格式:   • 单个整数:表示全

输入输出格式

输入格式:

 

• 第一行:单个整数N,1 ≤ N ≤ 30000

• 第二行到第N 1 行:第i 1 行有七个整数Vi 和Xi,1 ≤ Vi ≤ 30000; 1 ≤ Xi ≤ 三千0

 

输出格式:

 

• 单个整数:表示全数水牛发生的高低之和

 

输入输出样例

输入样例#1: 复制

4
3 1
2 5
2 6
4 3

输出样例#1: 复制

57

标题陈诉

John的N 头白牛每年都会在座“哞哞大会”。哞哞大会是红牛界的盛事。集会上的位移很

多,举例堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时集聚在一块儿,第i 头红牛的坐标为Xi,未有四头白牛的坐标是一模一样的。白牛们的叫声相当的大,第i 头和第j 头白牛调换,会生出max{Vi; Vj}×|Xi − Xj | 的轻重,个中Vi 和Vj 分别是第i 头和第j 头水牛的听力。假如每对红牛里面同一时间都在说话,请总括有所水牛发生的轻重之和是有一点点。

说明

朴素O(N2)

附近于归并排序的二分O(N logN)

树状数组O(N logN)

 

V* abs(a_1-X) V*abs(a_2-X) V*abs(a_3-X) ....
\=V*(abs(a_1-X) abs(a_2-X) abs(a_3-X) .......)
\
=V*(a_1-X a_2-X X-a_3)
\
=V*((-N*X (a_1 a_2 .. a_N)) M*X-(a_3 ...a_M)

推公式的标题
设当前白牛的高低为V,坐标为X,ai表示第i头白牛的坐标
假定a1,a2>X,a3<X(方便清楚)
咱俩发掘abs不知足分配率(正是abs(a b)!=abs(a) abs(b) )
此刻大家分景况切磋
存在n个白牛的坐标比X大,有m个白牛的坐标比X小,把地点的abs拆开

 图片 1

那么对于N,M,a1 a2 ...,a3 ,,,
接纳用树状数组求逆序对的思辨
大家得以用三个树状数组维护

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<deque>
 7 #include<queue>
 8 #define LL long long 
 9 #define lb(x)    ((x)&(-x))
10 using namespace std;
11 const LL MAXN=40000001;
12 inline LL read()
13 {
14     char c=getchar();LL x=0,f=1;
15     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
16     while(c>='0'&&c<='9')    x=x*10 c-48,c=getchar();return x*f;
17 }
18 struct node
19 {
20     LL v,x;
21 }cow[MAXN];
22 LL n;
23 int    comp(const node &a,const node &b)
24 {
25     return a.v<b.v;
26 }
27 LL tree_num[MAXN];
28 LL tree_sum[MAXN];
29 LL MAXX;
30 inline void Point_Add(LL pos,LL val,bool how)
31 {
32     while(pos<=MAXX)    
33     {
34         if(how==1)tree_num[pos] =val;
35         else tree_sum[pos] =val;
36         pos =lb(pos);
37     }
38 }
39 inline LL Interval_Ask(LL pos,bool how)
40 {
41     LL ans=0;
42     while(pos)
43     {
44         if(how==1) ans=ans tree_num[pos];
45         else ans=ans tree_sum[pos];
46         pos-=lb(pos);
47     }
48     return ans;
49 }
50 int main()
51 {
52     n=read();
53     for(LL i=1;i<=n;i  )    cow[i].v=read(),cow[i].x=read(),MAXX=max(MAXX,cow[i].x);
54     sort(cow 1,cow n 1,comp);
55     LL ans=0;
56     for(LL i=1;i<=n;i  )
57     {
58         // 1:数量   0:和 
59         ans =cow[i].v*(  ( -cow[i].x*( Interval_Ask(MAXX,1)-Interval_Ask(cow[i].x,1) )   (Interval_Ask(MAXX,0)-Interval_Ask(cow[i].x,0)) ) 
60                           cow[i].x*Interval_Ask(cow[i].x,1)-(Interval_Ask(cow[i].x,0)) );
61         Point_Add(cow[i].x,1,1);
62         Point_Add(cow[i].x,cow[i].x,0);
63     }
64     printf("%lld",ans);
65     return 0;
66 }

 

难题背景

MooFest, 2004 Open

本文由68399皇家赌场发布于集成经验,转载请注明出处:奶牛集会

关键词: 68399皇家赌场

上一篇:皇家国际娱乐平台:双冒号&quot;::&quot;

下一篇:没有了

频道精选

最火资讯