poj 3040 Allowance

知识点：

贪心

解题报告

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <limits>

using namespace std;

struct Coin {
  int d;
  int b;
};

bool cmp(const Coin &a, const Coin &b) {
  return a.d > b.d;
}

vector<Coin> v;
int N, C;
int need_count[20];

int main() {
  scanf("%d %d", &N, &C);
  int res = 0;
  for(int i=0;i<N;i++) {
    struct Coin c;
    scanf("%d %d", &c.d, &c.b);
    if (c.d >= C) {
      res += c.b;
      continue;
    }
    v.push_back(c);
  }

  sort(v.begin(), v.end(), cmp);
  N = v.size();

  int i, j;
  while(1) {
    int sum = C;
    memset(need_count, 0, sizeof(need_count));
    // 从大到小贪到刚好 sum 或是接近 sum
    for(i=0;i<N;++i) {
      if (sum > 0 && v[i].b > 0) {
        int has = min(v[i].b, sum / v[i].d);
        if (has > 0) {
          sum -= has * v[i].d;
          need_count[i] = has;
        }
      }
    }

    // 从小到大贪到 sum
    for(i=N-1;i>=0;--i) {
      if (sum > 0 && v[i].b > 0) {
        // 允许超过一个面值来凑够 sum
        int has = min(v[i].b - need_count[i], (sum+v[i].d-1) / v[i].d);
        if (has > 0) {
          need_count[i] += has;
          sum -= has * v[i].d;
        }
      }
    }

    if (sum > 0) break;

    int weeks = numeric_limits<int>::max();
    for(i=0;i<N;++i) {
      if (need_count[i] == 0) continue;
      // 对 C 的最优解所能满足的次数，即 weeks
      weeks = min(weeks, v[i].b / need_count[i]);
    }
    res += weeks;
    // 最后更新剩余金币数量
    for(i=0;i<N;++i) {
      if (need_count[i] == 0) continue;
      v[i].b -= weeks * need_count[i];
    }
  }
  
  printf("%d\n", res);
  return 0;
}

结语

经典贪心好题，重点学习贪心的思维方式