题意：题意：FJ有n头牛，排列成一条直线(不会在同一个点)，给出每头牛在直线上的坐标x。另外，每头牛还有一个自己的声调v，如果两头牛(i和j)之间想要沟通的话，它们必须用同个音调max(v[i],v[j])，沟通起来消耗的能量为：max(v[i],v[j]) * 它们之间的距离。问要使所有的牛之间都能沟通(两两之间)，总共需要消耗多少能量。
这个题看着数据量挺吓人的，但是只要肯动笔，这题其实很水的。
思路：
这个题目n^2的肯定能做，TLE呗，所以我们思考如何降低复杂度。
开始动笔：
设消耗的总能量为ans，则ans=sigma(max(v[i],v[j])*abs(x[j]-x[i])) 1<=i<j<=n
这个式子是没法化简的，原因有两个：
①包含max函数
②包含绝对值
那既然他们妨碍我们，我们就要想办法把他们去掉，首先对付max函数
这个大家应该很容易想到，因为i<j，排序一下不就保证v[i]<v[j]了吗？
按照x由小到大排序
ans=sigma(v[j]*abs(x[j]-[i])) 1<=i<j<=n
现在就要专心对付绝对值，想必大家初中老师都告诉过大家如何去绝对值——分类讨论
ans=sigma(v[j]*(fn[j]*x[j]-fx[j]+bx[j]-bn[j]*x[j])) 1<=i<j<=n 1<=k<j<=n
其中fn[j]为满足v[j]>=v[i]且x[i]<=x[j]的奶牛数量，即排序后在j之前的坐标小于j的奶牛数量
bn[j]为满足v[j]>=v[i]且x[i]>x[j]的奶牛数量，即排序后在j之前的坐标大于j的奶牛数量
fx[j]=fn[j]*x[i]
bx[j]=bn[j]*x[k]
这样推到基本就完成了，因为fn和bn都是动态变化的，所以我们要找一种数据结构帮助我们很快的查询——树状数组（应该能想到了）
将数组下标与奶牛的坐标对应，建立两个树状数组：
①num[i],存储i坐标是否已经放置了奶牛，很方便通过前缀和算出fn[j]，然后bn[j]=j-1-fn[j]
②sx[i]，存储i坐标的奶牛的坐标，可以计算出fx[j]，然后bx[j]=sumsx-fx[j]
其中sumsx是前i-1个奶牛的坐标的和
具体还是看代码吧~
表达能力不行，只能描述到这种地步了。。
View Code
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 6 #define N 25000 7 8 using namespace std; 9 10 struct COW 11 { 12 __int64 v,x; 13 }cow[N]; 14 15 __int64 n,num[N],sx[N]; 16 17 inline bool cmp(const COW &a,const COW &b) 18 { 19 return a.v<b.v; 20 } 21 22 void read() 23 { 24 for(__int64 i=1;i<=n;i++) scanf("%I64d%I64d",&cow[i].v,&cow[i].x); 25 sort(cow+1,cow+1+n,cmp); 26 memset(sx,0,sizeof sx); 27 memset(num,0,sizeof num); 28 } 29 30 inline __int64 lowbit(__int64 x) 31 { 32 return x&-x; 33 } 34 35 inline void updata(__int64 *a,__int64 x,__int64 dt) 36 { 37 while(x<N) 38 { 39 a[x]+=dt; 40 x+=lowbit(x); 41 } 42 } 43 44 inline __int64 getsum(__int64 *a,__int64 x) 45 { 46 __int64 rt=0; 47 while(x) 48 { 49 rt+=a[x]; 50 x-=lowbit(x); 51 } 52 return rt; 53 } 54 55 void go() 56 { 57 __int64 ans=0; 58 __int64 sumsx=0;//前i头牛的坐标和 59 __int64 forwardnum,backwardnum;//i以前的牛的个数 ，i以后的牛的个数 60 __int64 forwardsx,backwardsx;//i以前的牛坐标总和 ，i以后的牛坐标总和 61 for(__int64 i=1;i<=n;i++) 62 { 63 forwardnum=getsum(num,cow[i].x);//num没有更新呢！ 64 backwardnum=i-1-forwardnum; 65 66 forwardsx=getsum(sx,cow[i].x); 67 backwardsx=sumsx-forwardsx;//sumsx没有更新呢！ 68 69 ans+=cow[i].v*(forwardnum*cow[i].x-forwardsx+backwardsx-backwardnum*cow[i].x); 70 71 updata(sx,cow[i].x,cow[i].x); 72 updata(num,cow[i].x,1); 73 sumsx+=cow[i].x; 74 } 75 printf("%I64d\n",ans); 76 } 77 78 int main() 79 { 80 while(scanf("%I64d",&n)!=EOF) 81 { 82 read(); 83 go(); 84 } 85 return 0; 86 }
决定以后多写题解，一是锻炼我的表达能力，二是对题目增加更深层次的认识！