poj1018 Communication System ——贪心+枚举

May 25, 2013
POJ

题目链接：http://poj.org/problem?id=1018 题目大意：　　有n种设备，每种设备有mi个选择，每种设备选择一个，每个设备都有一个带宽值和价钱，要求每种设备选择一个，最终选择的n个设备里面，带宽B是这n个设备里面所有带宽的最小值吗，价钱P为这n个设备价钱的和，求B/P的最大值。题目思路：　　这题开始没读懂题意，后来搜的题意之后才明白。然后没有思路……看了人家的思路，貌似懂了……然后就开始写，写跪了……开始的方法是，求出所有这n种设备里面每种设备的带宽的最小值，依次枚举这些最小值就可以了。总是WA…… 　　昨天纠结一晚上，今天早上又想了一下，发现原来的想法是有问题的，应该一直枚举到所有n中设备里面每种带宽的最大值的最小值。第一：保证这n种设备每一种都可以选上。第二：虽然枚举的B值比原来大了，所得到的的价钱不小于我原来的做法所得到的的价钱，但是，重点来了：B也增大了啊！有木有！所以，这就是我当初没有想到的！


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 0x7fffffff
#define MINN -MAXN
const int MAX = 100+10;
typedef struct node {
  int p, b, cnt;
  bool operator < (const node & other ) const {
    if (p != other.p) return p < other.p;
    else return b < other.b;
  }
}node;
typedef struct sys {
  node de[MAX];
  int Min, Max, cnt;
  bool operator < (const sys &other) const {
    return Min < other.Min;
  }
}sys;
sys ban[MAX];
void solve() {
  int n; scanf("%d", &n);
  int i, j, tMin, tMax, sump, k;
  double ans;
  for (i = 0; i < n; ++i) {
    scanf("%d", &ban[i].cnt);
    tMin = MAXN; tMax = MINN;
    for (j = 0; j < ban[i].cnt; ++j) {
      scanf("%d%d", &ban[i].de[j].b, &ban[i].de[j].p);
      if (tMin > ban[i].de[j].b) tMin = ban[i].de[j].b;
      if (tMax < ban[i].de[j].b) tMax = ban[i].de[j].b;
    }
    ban[i].Min = tMin; ban[i].Max = tMax;
    sort(ban[i].de, ban[i].de + ban[i].cnt);
  }
  sort(ban, ban+n);
  int start, end; start = ban[0].Min; end = MAXN;
  for (i = 0; i < n; ++i) {
    if (end > ban[i].Max) end = ban[i].Max;
  }
  ans = MINN;
  for (i = start; i <= end; ++i) {
    sump = 0;
    for (j = 0; j < n; ++j) {
      k = 0;
      while (ban[j].de[k].b < i) ++k;
      sump += ban[j].de[k].p;
    }
    double re = (double)i/(double)sump;
    if (re > ans) ans = re;
  }
  /*
  for (i = 0; i < n; ++i) {
    sump = 0;
    int tmp = ban[i].Min; 
    bool mrk = true;
    for (k = 0; k < n; ++k) {
      if (ban[k].Max < tmp) {mrk = false; break;}
      j = 0;
      while (ban[k].de[j].b < tmp) j++;
      sump += ban[k].de[j].p;
    }
    if (!mrk) continue;
    double re = (double)tmp/(double)sump;
    //cout << "tmp = " << tmp << endl;
    //cout << "sump = " << sump << endl;
    if (re > ans) ans = re;
  }
  */
  printf("%.3f\n", ans);
}
void init() {
  //freopen("1018.in", "r", stdin);
  int t; scanf("%d", &t);
  while (t--) {
    solve();
  }
}
int main(void) {
  init();
  return 0;
}

调试的时候的注释就不删了……都是血淋淋的教训好吧，我的做法是有多繁琐……人家的代码都超短o(╯□╰)o

Read more