P2345-[USACO04OPEN]MooFest G
题目:
题目描述:
约翰的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:
1
2
3
4
5
| 4
3 1
2 5
2 6
4 3
|
样例输出1:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include "ybwhead/ios.h"
using namespace std;
const int maxn = 1e5 + 10;
struct node
{
int v, x;
} a[maxn], tmp[maxn];
int cmp(node a, node b)
{
return a.v < b.v;
}
long long ans, n;
void cdq(int l, int r)
{
if (l >= r)
return;
int mid = (l + r) >> 1, ll = l;
cdq(l, mid);
cdq(mid + 1, r);
long long s2, s1;
s1 = s2 = 0;
for (int i = l; i <= mid; i++)
s1 += a[i].x;
for (int i = mid + 1; i <= r; i++)
{
while (ll <= mid && a[ll].x < a[i].x)
{
s2 += a[ll].x;
s1 -= a[ll].x;
ll++;
}
ans += (1ll * a[i].x * (ll - l) - s2 - 1ll * a[i].x * (mid - ll + 1) + s1) * a[i].v;
}
int l1 = l, l2 = mid + 1, k = l - 1;
while (l1 <= mid || l2 <= r)
{
if ((a[l1].x > a[l2].x || l1 > mid) && l2 <= r)
{
tmp[++k] = a[l2];
l2++;
}
else
{
tmp[++k] = a[l1];
l1++;
}
}
for (int i = l; i <= r; i++)
a[i] = tmp[i];
}
int main()
{
yin >> n;
for (int i = 1; i <= n; i++)
{
yin >> a[i].v >> a[i].x;
}
sort(a + 1, a + n + 1, cmp);
cdq(1, n);
yout << ans << endl;
return 0;
}
|