[每日一题] [NC25043] Protecting the Flower

题目大意：有一些奶牛，每个奶牛有两个属性，一个是Ti，一个是Di。需要选择一个所有奶牛的排列，使得以下的值最小：每个奶牛被选中时，加上Ti和所有尚未被选中的Di的总和。
例如T1=D1=D2=2,T2=3时，如果先选择1，该总和为T1D2=4，如果先选择2，该总和为T2D1=6，则12顺序优于21顺序。

https://ac.nowcoder.com/acm/problem/25043

分析相邻两个奶牛，用哪一个顺序更优：
cow1: D1, T1
cow2: D2, T2
按照cow1,cow2的顺序，这两个奶牛的贡献为：
2T1(D - D1) + 2T2(D - D1 - D2)
= 2(T1+T2)D - 2T1D1-2T2D2-2T2D1
同理，反过来的贡献为：
2(T1 + T2)D - 2T1D1-2T2D2-2T1D2

对于最优解中相邻的奶牛cow1,cow2，应该满足该顺序优于cow2, cow1，即
-2T2D1 < -2T1D2 <=> T1/D1<T2/D2.

int main(int argc, char* argv[]) {
  /* Do not use for codejam. */
  /* ios_base::sync_with_stdio(false); cin.tie(NULL); */
  readint(N);
  readvpii(cows, N);
  sort(ALL(cows), [](const PII& cow1, const PII& cow2) {
    return ll(cow1.FI) * ll(cow2.SE) < ll(cow1.SE) * ll(cow2.FI);
  });
  ll ans = 0;
  ll sum_D = 0;
  REP(i, N) {
    sum_D += cows[i].SE;
  }
  REP(i, N) {
    sum_D -= cows[i].SE;
    ans += sum_D * 2 * ll(cows[i].FI);
  }
  printlong(ans);
  return 0;
}