首页 > 代码库 > 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 输出格式: ? 单个整数:表示所有奶牛产生的音量之和 输入输出样例 输入样例#1: 4 3 1 2 5 2 6 4 3 输出样例#1: 57 说明 朴素O(N2) 类似于归并排序的二分O(N logN) 树状数组O(N logN)
题目描述 一群青年人排成一队,用手机互相聊天。 每个人的手机有一个信号接收指标,第i个人的接收指标设为v[i]。 如果位置在x[i]的人要和位置在xj的人聊天,那么这两人组成的一对的信号发射强度就是abs(x[i]-x[j])*max(v[i],v[j]). 现在我们想知道,这些人所有对子中的信号发射强度的总和。 输入输出格式 输入格式: 第一行一个整数N,接下来N行,每行两个整数v[i]和x[i]。 输出格式: 所有对的信号发射强度总和。 输入输出样例 输入样例#1: 4 3 1 2 5 2 6 4 3 输出样例#1: 57 说明 对于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 低头一族
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。