POJ 1018 离散最优化枚举

#include <cstdio>#include <iostream>#include <algorithm>#include <queue>#include <stack>#include <cstdlib>#include <cmath>#include <set>#include <map>#include <vector>#define INF 100000000using namespace std;struct node{int b,p;bool operator <(const node& a)const{if(b == a.b){return p < a.p;}else{return b < a.b;}}};node a[105][105];int m[105];int main(){int t;cin >> t;while(t–){int n;cin >> n;set<int> se;for(int i = 0;i < n;i++){scanf("%d",&m[i]);for(int j = 0;j < m[i];j++){scanf("%d%d",&a[i][j].b,&a[i][j].p);if(se.find(a[i][j].b) == se.end()){se.insert(a[i][j].b);}}sort(a[i],a[i]+m[i]);}set<int>::iterator ite = se.begin();double ans = 0;for(ite = se.begin();ite != se.end();ite++){node q;q.b = *ite;q.p = 0;int p = 0;int flag = 0;for(int i = 0;i < n;i++){int x = INF;for(int j = 0;j < m[i];j++){if(a[i][j].b >= q.b){if(a[i][j].p < x){x = a[i][j].p;}}}if(x == INF){flag = 1;}else{p += x;}}if(flag){break;}else{ans = max(ans,q.b*1.0/p);}}printf("%.3lf\n",ans); }return 0;}

,他们不计后果的彼此拥抱,握紧双手,怕天会亮,怕爱会走。

POJ 1018 离散最优化枚举

相关文章:

你感兴趣的文章:

标签云: