| ||||||||||
| 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 | |||||||||
Re:一开始用O(n^2)的方法TLE死了,后来发现有O(N)的算法,试探着写了一下,居然AC了In Reply To:一开始用O(n^2)的方法TLE死了,后来发现有O(N)的算法,试探着写了一下,居然AC了 Posted by:Sempr at 2006-03-13 21:28:32 想请教下,你用的什么算法,我写的程序TLE了,这个是我的源代码,思路很平常:
#include <stdio.h>
int main()
{
int textCnt;
int a, b, m;
int dt[10001];
int total[10001];
int i, j;
int min;
int minIndex;
scanf("%d", &textCnt);
while(textCnt--)
{
//读入数据
scanf("%d%d%d", &m, &a, &b);
for(i = 1; i <= m; ++i)
{
scanf("%d", &dt[i]);
}
//穷举,每层都试
for(i = 1; i <= m; ++i)
{
total[i] = 0;
for(j = 1; j <= m; ++j)
{
if(j < i) //需要往楼下走
{
total[i] += dt[j] * ((i - j) * b + 0.5 * (i - j) * (i - j - 1));
}
else
{
total[i] += dt[j] * ((j - i) * a + 0.5 * (j - i) * (j - i - 1));
}
}
}
//寻找符合题目要求的结果
min = total[1];
minIndex = 1;
for(i = 2; i <= m; ++i)
{
if(total[i] < min)
{
min = total[i];
minIndex = i;
}
}
printf("%d\n", minIndex);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator