POJ1990 MooFest

嘟嘟嘟

题目大意：一群牛参加完牛的节日后都有了不同程度的耳聋（汗……），第i头牛听见别人的讲话，别人的音量必须大于v[i]，当两头牛i，j交流的时候，交流的最小声音为max{v[i],v[j]}*他们之间的距离。现在有n头牛，求他们之间两两交流最少要的音量和。

首先我们把v[i]从小到大排序，这样扫的时候max(v[i], v[j]) == v[i] (j < i)了。同时为了重复计算，我们只统计j < i的牛和 i 配对对答案的贡献。

关键是解决距离的绝对值的问题。用两个树状数组维护。

一个求对于当前的 i，dis[j] < dis[i]的牛有几头(cnt)，一个维护这些牛的Σval(_sum)。这样对于那些dis[j] < dis[i]的牛，对答案的贡献就是val[i] * (cnt * dis[i] - _sum)。对于那些dis[j] > dis[i]的牛，我们还要开一个全局变量sum，表示当前的Σval[i]，那么这这 j 头牛的sum' = sum - _sum, cnt' = (i - 1 - cnt)，所以这部分牛对答案的贡献就是val[i] * (sum' - cnt' * dis[i])。最后把两部分相加。

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<vector>

 #include<stack>

 #include<queue>

 using namespace std;

 #define enter puts("")

 #define space putchar(' ')

 #define Mem(a, x) memset(a, x, sizeof(a))

 #define rg register

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 const int maxn = 2e4 + ;

 inline ll read()

 {

   ll ans = ;

   char ch = getchar(), last = ' ';

   while(!isdigit(ch)) {last = ch; ch = getchar();}

   while(isdigit(ch)) {ans = ans *  + ch - ''; ch = getchar();}

   if(last == '-') ans = -ans;

   return ans;

 }

 inline void write(ll x)

 {

   if(x < ) x = -x, putchar('-');

   if(x >= ) write(x / );

   putchar(x %  + '');

 }

 int n;

 ll sum = , ans = ;

 struct Node

 {

   int val, id;

   bool operator < (const Node &oth)const

   {

     return val < oth.val || (val == oth.val && id < oth.id);

   }

 }a[maxn];

 struct Bit

 {

   ll c[maxn];

   Bit() {Mem(c, );}

   int lowbit(int x)

   {

     return x & -x;

   }

   void add(int pos, int d)

   {

     for(; pos < maxn; c[pos] += d, pos += lowbit(pos));

   }

   ll query(int pos)

   {

     ll ret = ;

     for(; pos; ret += c[pos], pos -= lowbit(pos));

     return ret;

   }

 }C1, C2;

 int main()

 {

   n = read();

   for(int i = ; i <= n; ++i) a[i].val = read(), a[i].id = read();

   sort(a + , a + n + );

   for(int i = ; i <= n; ++i)

     {

       int cnt = C1.query(a[i].id), _sum = C2.query(a[i].id);

       C1.add(a[i].id, ); C2.add(a[i].id, a[i].id);

       ll tot =  cnt * a[i].id - _sum;

       tot += sum - _sum - (i - cnt - ) * a[i].id;

       ans += tot * a[i].val;

       sum += a[i].id;

     }

   write(ans); enter;

   return ;

 }

巴特西

POJ1990 MooFest

最新文章

热门文章