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