poj 1990 MooFest(ツリー配列)
MooFest
Time Limit: 1000MS
Memory Limit: 30000K
Total Submissions: 6265
Accepted: 2765
Description
Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing.
Each cow i has an associated "hearing"threshold v(i) (in the range 1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by cow i. If two cows i and j wish to converse, they must speak at a volume level equal to the distance between them times max(v(i),v(j)).
Suppose each of the N cows is standing in a straight line (each cow at some unique x coordinate in the range 1..20,000), and every pair of cows is carrying on a conversation using the smallest possible volume.
Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows.
Input
* Line 1: A single integer, N
* Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the second cow; and so on. No two cows will stand at the same location.
Output
* Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows.
Sample Input
Sample Output
Source
USACO 2004 U S Open
牛の群れは牛の祝日に参加した后にすべて异なる程度の聴覚障害があって、第i头の牛は他の人の话を闻いて、他の人の音量はv[i]より大きくなければならなくて、2头の牛i,jが交流する时、交流の最小の音はmax{v[i],v[j]*彼らの间の距离です.今n頭の牛がいて、彼らの間の2つの交流の最も少ない音量とを求めます.
問題解決の構想:まず音量fに基づいて並べ替えて、このように最適化することができて、つまりある牛iにとって、彼の前に並ぶ音量はすべて彼より小さくて、きっとi自身の音量*の両者の間の距離を使うのです.このときの計算式は、(現在のxより小さいすべての和を解く)
(x-x1)*f;
(x-x2)*f;
(x-x3)*f........
総じて:(n*x(x 1+x 2+x 3+.....)*f; 注:xはある牛の現在の位置を表し、x 1,x 2,x 3......彼の前に並んでいる牛の位置を表すと、f現在の牛の音量は、彼が最大の音量だからだ.(ここの距離は木の配列で解く必要があります)
ここで説明しなければならないのは、この牛iの前に並んでいる音量はきっと彼より小さいに違いないが、座標値xは必ずしも彼より小さいとは限らないので、私たちは別々に処理するしかないということだ.
私たちは1つの数軸を創立することができて、1つの点の1つの点の入れることができて、先に入れる音量は間違いなく小さくて、彼をあるべき固定位置に従って入れて、このように彼の前に並ぶすべてのxはすべて彼より小さくて上の方法で木状の配列の方法を採用して区間の和を求めることができます.(ここには、左と右の値を1回解くと、左は現在のxより小さく、右は現在のxより大きい)を入れます.
現在の値xより大きい場合の計算方法を説明します.
(x1-x)*f;
(x2-x)*f;
(x3-x)*f........
以上:((x 1+x 2+x 3+......)-n*x)*f;
ここでのn値は、入ったすべての牛の個数に等しいはずです.前に計算した彼のxより小さい個数:i-nn;
(x1+x2+x3+...)合計から彼より小さいxの和を減算することに等しいはずです.
long long!!!
このように言うのはとても复雑で、详しくはコードの実现を见て~~~コメントが分かりません
詳細はコードを参照してください.
Time Limit: 1000MS
Memory Limit: 30000K
Total Submissions: 6265
Accepted: 2765
Description
Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing.
Each cow i has an associated "hearing"threshold v(i) (in the range 1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by cow i. If two cows i and j wish to converse, they must speak at a volume level equal to the distance between them times max(v(i),v(j)).
Suppose each of the N cows is standing in a straight line (each cow at some unique x coordinate in the range 1..20,000), and every pair of cows is carrying on a conversation using the smallest possible volume.
Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows.
Input
* Line 1: A single integer, N
* Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the second cow; and so on. No two cows will stand at the same location.
Output
* Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows.
Sample Input
4
3 1
2 5
2 6
4 3
Sample Output
57
Source
USACO 2004 U S Open
牛の群れは牛の祝日に参加した后にすべて异なる程度の聴覚障害があって、第i头の牛は他の人の话を闻いて、他の人の音量はv[i]より大きくなければならなくて、2头の牛i,jが交流する时、交流の最小の音はmax{v[i],v[j]*彼らの间の距离です.今n頭の牛がいて、彼らの間の2つの交流の最も少ない音量とを求めます.
問題解決の構想:まず音量fに基づいて並べ替えて、このように最適化することができて、つまりある牛iにとって、彼の前に並ぶ音量はすべて彼より小さくて、きっとi自身の音量*の両者の間の距離を使うのです.このときの計算式は、(現在のxより小さいすべての和を解く)
(x-x1)*f;
(x-x2)*f;
(x-x3)*f........
総じて:(n*x(x 1+x 2+x 3+.....)*f; 注:xはある牛の現在の位置を表し、x 1,x 2,x 3......彼の前に並んでいる牛の位置を表すと、f現在の牛の音量は、彼が最大の音量だからだ.(ここの距離は木の配列で解く必要があります)
ここで説明しなければならないのは、この牛iの前に並んでいる音量はきっと彼より小さいに違いないが、座標値xは必ずしも彼より小さいとは限らないので、私たちは別々に処理するしかないということだ.
私たちは1つの数軸を創立することができて、1つの点の1つの点の入れることができて、先に入れる音量は間違いなく小さくて、彼をあるべき固定位置に従って入れて、このように彼の前に並ぶすべてのxはすべて彼より小さくて上の方法で木状の配列の方法を採用して区間の和を求めることができます.(ここには、左と右の値を1回解くと、左は現在のxより小さく、右は現在のxより大きい)を入れます.
現在の値xより大きい場合の計算方法を説明します.
(x1-x)*f;
(x2-x)*f;
(x3-x)*f........
以上:((x 1+x 2+x 3+......)-n*x)*f;
ここでのn値は、入ったすべての牛の個数に等しいはずです.前に計算した彼のxより小さい個数:i-nn;
(x1+x2+x3+...)合計から彼より小さいxの和を減算することに等しいはずです.
long long!!!
このように言うのはとても复雑で、详しくはコードの実现を见て~~~コメントが分かりません
詳細はコードを参照してください.
#include
#include
#include
#include
using namespace std;
#define ll long long
struct node
{
ll f,x;
} s[20010];
int n;
ll c1[20010],c2[20010];
ll a1[20010],a2[20010];
bool cmp(node a,node b)
{
return a.f