Poj 3262 Protecting the Flowers

原题地址

知识点：贪心

解题报告

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct P {
  int t, d;
};

// 贪心使得代价最小
// cost = 2 * T * (total - D)
// 因此 D越大，T越小越好
// 重点：转换成 D / T 越大越好
bool cmp(const P &a, const P &b) {
  return b.d * a.t < a.d * b.t;
}

vector<P> v;

int N;

int main() {
  scanf("%d", &N);
  int i, total;
  total = 0;
  for(i=0;i<N;++i) {
    struct P p;
    scanf("%d %d", &p.t, &p.d);
    v.push_back(p);
    total += p.d;
  }

  sort(v.begin(), v.end(), cmp);  
  unsigned long long res = 0;
  for(i=0;i<N;++i) {
    total -= v[i].d;
    res += total * v[i].t * 2;
  }

  cout << res << endl;
  return 0;
}