Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:一开始用O(n^2)的方法TLE死了,后来发现有O(N)的算法,试探着写了一下,居然AC了

Posted by Pro_zq at 2009-08-17 14:57:35 on Problem 1701
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator