| 题目名称 | 1385. 开会的鱼儿 |
|---|---|
| 输入输出 | fishb.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cqw
于2013-06-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：9， 通过率：22.22% | ||||
 HouJikan |
100 | 0.254 s | 4.22 MiB | C++ |
 了反取字名我擦 |
100 | 0.652 s | 6.42 MiB | C++ |
|
了反取字名我擦 |
50 | 0.938 s | 7.94 MiB | C++ |
|
了反取字名我擦 |
50 | 0.960 s | 9.47 MiB | C++ |
 Ezio |
50 | 10.999 s | 0.62 MiB | C++ |
 STARGAZER |
50 | 11.139 s | 0.50 MiB | C++ |
|
STARGAZER |
50 | 11.186 s | 0.47 MiB | C++ |
|
STARGAZER |
20 | 0.853 s | 0.31 MiB | C++ |
|
STARGAZER |
20 | 7.277 s | 0.45 MiB | C++ |
| 本题关联比赛 | |||
| 20130601 | |||
| 关于 开会的鱼儿 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
各种不好做。。
两个树状数组，一个维护小于X的所有鱼的X的和，一个维护小于X的鱼的个数。。 把鱼按照V排好序就行了。。 | ||||
|
树状数组，╮(╯▽╰)╭。
Ezio
2014-09-26 23:03
1楼
| ||||
【题目描述】
jzyz的池塘里的鱼是用魔法交流的。六一要到了，鱼儿们也要开一个聚会，聚会前，他们决定开会讨论一下聚会的安排，N（1<=N<=40000）条鱼都参加了这次讨论会。
为了让你计算方便，鱼儿们决定站成一条直线来进行开会，每条鱼的位置为Xi(1<=Xi<=20000)，而每条鱼都有一定的魔法值Vi(1<=Vi<=20000)，如果两条鱼想交流，他们需要花费的能量必须要大于等于
max（Vi,Vj） *dist(i,j)
max表示 Vi和Vj的最大值， dist(i，j)表示第i条鱼和第j条鱼之间的距离。
现在，鱼儿们想知道，如果每对鱼儿都要交流，并且使用最小的能量，所有
(N*(N-1))/2 对鱼儿 花费能量之和的最小值是多少。
【输入格式】
第一行：一个正整数N。
接下来N行，每行两个整数，表示Vi和Xi。
【输出格式】
一个整数，表示最小能量花费。
【样例输入】
4 3 1 2 5 2 6 4 3
【样例输出】
57
【提示】
在此键入。
【来源】
在此键入。