Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
蒟蒻的AC纪念//784K 63ms //大致思路是 //在每个种类中,由小到大枚举最小带宽,然后由大到小遍历出最小价格和。 //枚举最小带宽时,若出现无法满足每个种类都选择的情况,则跳到下一个种类枚举。遍历时若当前设备带宽小于最小带宽,则同样跳到下个种类。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <ctype.h> using namespace std; const int MAXDEVICE = 10000; const int MAXN = 100; struct node{ int wid; int pri; int id; }device[MAXDEVICE+1]; bool _cmp(node x, node y) { if (x.id != y.id) return x.id < y.id; else if (x.wid != y.wid) return x.wid > y.wid; else return x.pri < y.pri; } int skip_white() { int c; while ( (c=getchar()) != EOF && c==' ') c = getchar(); return c; } void Myscan(int *n) { int c; int last = skip_white(); *n = (isdigit(last)) ? last-'0' : 0; while ( (c=getchar()) != EOF && isdigit(c)) *n = *n * 10 + c - '0'; } int main() { int t; int n; int mi; int i, j; int id; int conwid; int minofmax; int mark = 0; int conpri = 0; int totpri = 0; int count = 0; float temp; float ans = 0.0; int jump[MAXN+1]; Myscan(&t); while (t--) { memset(device, 0, sizeof(device)); memset(jump, 0, sizeof(jump)); ans= 0.0; count = 0; Myscan(&n); for (i = 1; i <= n; i++) { Myscan(&mi); for (j = 1; j <= mi ;j++) { ++count; Myscan(&device[count].wid); Myscan(&device[count].pri); device[count].id = i; } } sort(device+1, device+count+1,_cmp); mark = 0; for (i = 1; i <= count; i++) { id = device[i].id; if (id > mark) { jump[id] = i; mark++; } } for (i = count; i >= 1; i--) { id = device[i].id; conwid = device[i].wid; conpri = 0; totpri = 0; mark = 0; for (j = 1; j <= count; j++) { if (device[j].wid < conwid) { if (device[j].id == mark) { j = jump[mark+1] - 1; continue; } else break; } else { if (device[j].id == mark) conpri = (device[j].pri < conpri) ? device[j].pri : conpri; else { mark++; totpri += conpri; conpri = device[j].pri; } } } if (mark == n) { totpri += conpri; temp = (float)conwid/(float)totpri; ans = (temp > ans) ? temp : ans; } else i = jump[id] ; } printf("%.3f\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator