| ||||||||||
| 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