洛谷P2345 奶牛集会
2018-06-17 21:42:33来源:未知 阅读 ()
题目背景
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
输出格式:
• 单个整数:表示所有奶牛产生的音量之和
输入输出样例
4 3 1 2 5 2 6 4 3
57
说明
朴素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拆开
那么对于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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash