题外话:POJ 2231 Moo Volume
题意：解题过程：AC代码：
题外话:
emm……第三套题好像综合了其他OJ的题目蛤，那么我就把题目分开了发了蛤蛤……
POJ 2231 Moo Volume
题目传送门
题意：
你有一个牛庄，牛庄中总共有n头牛，在晚上，每两头牛都会进行交谈，而交谈的声音的音量就是这两头牛的距离，给出你这n头牛各自的位置，让你求在晚上这些牛发出的总音量。
解题过程：
看了题目发现n有100000，所以暴力是肯定过不了的，那么我们就可以考虑另一种类似公式递推的方法，我们先对所有牛按照位置进行排序，然后假设F[i]表示第i头牛与其他牛交谈发出的总音量，然后对于第i+1头牛，我们设一个d值，代表第i头牛与第i+1头牛之间的距离，那么对于第i+1头牛之前的牛j，与第i+1头牛交谈产生的音量值就是第i头牛与第j头牛交谈的音量+d，同样，对于第i+1头牛之后的牛j，与第i+1头牛交谈产生的音量值就是第i头牛与第j头牛交谈的音量-d，所以我们可以得出递推式F[i+1]=F[i]+d*(i-1)+d*(n-i+1)，这样O（n）递推下去就行了，最后把音量值加起来就是所求的答案了。
AC代码：
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=
100005;
int n;
ll a[maxn];
ll f[maxn];
int main() {
scanf(
"%d",&n);
for(
int i=
1;i<=n;i++) {
scanf(
"%lld",&a[i]);
}
sort(a+
1,a+
1+n);
for(
int i=
1;i<=n;i++) {
f[
1]+=a[i]-a[
1];
}
ll ans=f[
1];
for(
int i=
2;i<=n;i++) {
ll d=a[i]-a[i-
1];
f[i]=f[i-
1]+d*(i-
1)-d*(n-i+
1);
ans+=f[i];
}
printf(
"%lld\n",ans);
return 0;
}
本人蒟蒻OIer一枚，欢迎加QQ：840776708一起学习蛤。
转载于:https://www.cnblogs.com/Apocrypha/p/9433672.html
