树状数组题目
暴力做法
直接暴力求解，依次算距离和最大v。
时间复杂度
时间复杂度为O(n2)
其中占时间最多的乘法次数是 n*(n-1)/2，时间复杂度是O(n2)。
#pragma warning(disable:4996)
#include <stdio.h>
int main(void)
{
// freopen("q.txt", "r", stdin);
int N, n, i, j;
int *v, *p;
unsigned long long sum;
v = new int[20000];
p = new int[20000];
scanf("%d", &N);
for (n = 0, sum = 0; n < N; n++) {
scanf("%d %d", &v[n], &p[n]);
for (i = 0; i < n; i++) {
j = p[n] - p[i];
sum += (v[n] > v[i] ? v[n] : v[i]) * (j >= 0 ? j : -j);
}
}
printf("%I64d\n", sum);
delete[] v;
delete[] p;
return 0;
}
优化1 减少乘法次数
先根据v降序排序，这样对于cow[i]，和就等于i<j<n的所有奶牛到它的距离之和 乘 cow[i].v
时间复杂度
新增排序的时间复杂度是O(nlogn)，乘法的复杂度降低到O(n)
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
typedef struct _COW {
int v;
int p;
}COW, *PCOW;
int cmp(const void* a, const void* b) {
return PCOW(b)->v - PCOW(a)->v;
}
int main(void)
{
// freopen("q.txt", "r", stdin);
int N, n, i, j;
PCOW cows;
unsigned long long sum, d;
scanf("%d", &N);
cows = new COW[N];
for (n = 0; n < N; n++) {
scanf("%d %d", &cows[n].v, &cows[n].p);
}
qsort(cows, N, sizeof(COW), cmp);
for (sum = 0, i = 0; i < N; i++) {
for (d = 0, j = i + 1; j < N; j++) {
d += abs(cows[i].p - cows[j].p);
}
sum += d * cows[i].v;
}
printf("%I64d\n", sum);
delete[] cows;
return 0;
}
优化2 减少计算距离和的计算量
首先cows改为升序。
通过维护两个树状数组，减少计算cows[i]到其他奶牛距离总和时的计算量。
第一个树状数组原数组count[p]表示坐标为p的奶牛i是否已经计算 v[i]*sum(d[j])（v[j] < v[i]）。
第二个树状数组原数组dist[p]表示当count[p] = 1即该奶牛已经计算过时，dist[p] = p。如果该奶牛没计算，则dist[p] = 0。
如此一来，当计算第i个奶牛时，count左边和 就是左边奶牛的个数。
左边距离之和为 leftDistSum = sum(p - p[i]) = sum(p) - sum(p[i]) （p[i] < p）。
最终左右距离之和为 sumDist = (p*count左边和 - dist左边和) + (dist右边和 - p*count右边和)。
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#define MAX 20001
typedef unsigned long long ull;
int maxP = 0;
ull count[MAX], dist[MAX];
typedef struct _COW {
int v;
int p;
}COW, *PCOW;
int cmp(const void* a, const void* b) {
return PCOW(a)->v - PCOW(b)->v;
}
ull bitSum(ull* bit, int i)
{
ull s = 0;
while (i > 0) {
s += bit[i];
i -= i & -i;
}
return s;
}
ull bitSumR(ull* bit, int i)
{
return bitSum(bit, MAX-1) - bitSum(bit, i - 1);
}
void bitAdd(ull* bit, int i, ull x)
{
while (i < MAX) {
bit[i] += x;
i += i & -i;
}
}
int main(void)
{
// freopen("q.txt", "r", stdin);
int N, n, i, j;
PCOW cows;
unsigned long long sum, d;
scanf("%d", &N);
cows = new COW[N];
for (n = 0; n < N; n++) {
scanf("%d %d", &cows[n].v, &cows[n].p);
}
qsort(cows, N, sizeof(COW), cmp);
for (sum = 0, i = 0; i < N; i++) {
int p = cows[i].p;
ull leftD = p * bitSum(count, p) - bitSum(dist, p);
ull rightD = bitSumR(dist, p) - p * bitSumR(count, p);
sum += (leftD + rightD) * cows[i].v;
bitAdd(count, p, 1);
bitAdd(dist, p, p);
}
printf("%I64d\n", sum);
delete[] cows;
return 0;
}
