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 |
郁闷啊,我用O(knlogn)的算法,怎么会超时啊,有谁能帮我看一下#include <iostream> #include <cstdio> #include <algorithm> using namespace std; struct Array { int x; int s; }; Array array[30]; int n,h; int fi[30],di[30],ti[30]; int andy[30],sum[30]; int input( ) { int i; scanf("%d",&h); h *= 60; for(i = 0;i < n;i ++) scanf("%d",&fi[i]); for(i = 0;i < n;i ++) scanf("%d",&di[i]); ti[0] = 0; for(i = 1;i < n;i ++) scanf("%d",&ti[i]); return 0; } bool cmp(Array a,Array b) { return (a.x < b.x || (a.x == b.x && a.s > b.s)); } int compute(int limite,int len) { int add,a,b; add = 0; make_heap(array,array + len,cmp); while(limite) { if(len == 0) { andy[0] += limite; return add; } pop_heap(array,array + len,cmp); a = array[-- len].x; b = array[len].s; add += a; andy[b] += 5; a -= di[b]; if(a < 0) a = 0; limite -= 5; if(a == 0) continue; array[len].s = b; array[len ++].x = a; push_heap(array,array + len,cmp); } return add; } bool compare() { int i; for(i = 0;i < n;i ++) { if(andy[i] < sum[i]) return false; if(andy[i] > sum[i]) return true; } return false; } int solution( ) { int j,i,limite,result,ttp; ttp = 0; limite = h; for(i = 0;i < n;i ++) { limite -= 5 * ti[i]; for(j = 0;j <= n;j ++) { array[j].x = fi[j]; array[j].s = j; andy[j] = 0; } result = compute(limite,i + 1); if(result > ttp) { ttp = result; for(j = 0;j < n;j ++) sum[j] = andy[j]; } else if(result == ttp && compare()) for(j = 0;j < n;j ++) sum[j] = andy[j]; } printf("%d",sum[0]); for(i = 1;i < n;i ++) printf(", %d",sum[i]); printf("\n"); printf("Number of fish expected: %d\n",ttp); return 0; } int main( ) { freopen("input.txt","r",stdin); freopen("out.txt","w",stdout); int i = 0; for(;;) { scanf("%d",&n); if(n == 0) break; if(i == 0) i = 1; else printf("\n"); input( ); solution( ); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator