排队I(替换两层复杂for循环、避免TLE)

问题 C: 排队I(点击)

时间限制: 1 Sec  内存限制: 128 MB

提交: 391  解决: 49

  [提交] [状态] [讨论版] [命题人:admin]

题目描述

楠楠最近在研究南海区5年级英语成绩的排序有关算法，如果数列中的数是从小到大排列的，则称有序的。研究中对于没有排好序的数列，要统计每个数前面有多少比它大的数字。比如有5个数的数列： 3 1 4 2 5，则第1个数3之前有0个数比它大；第2个数1之前有1个数比它大；第3个数4之前有0个数比它大；第4个数2之前有2个数比它大；第5个数5之前有0个数比它大。由于数列很长，楠楠求你编程来统计。

输入

第一行1个整数N，表示数列有N个整数。

第二行有N个非负整数，每个数表示一个分数，范围是[0…120]。

输出

一行N个非负整数(每个非负整数后面有一个空格)，第i个数表示原数列中第i位前有多少比第i位数大。

样例输入

复制样例数据

5

3  1  4  2  5

样例输出

0 1 0 2 0

提示

8个的数据： N的范围是[1…1000]，每个数范围是[0…120]

2个的数据：N的范围是[1…1,00,000]，每个数范围是[0…120]

之前做过一次和这个几乎一样的题目但是之前的题目数据没有那么大所以未出现tle 也就没考虑用神么方法优化一下比赛完也没想到好的思路看了博客学到种方法可惜我把数组大小开反了也没提示运行错误所以也没注意是数组问题最后从头读了下代码才发现

思路：

记录输入的数m 每次输入一个数就用 for去从m+1 开始遍历到120

如果m+1这个值超过0个就把他的数目加入count中

代码：

#include<stdio.h>

int main()

{

    int n,i,m,j;

    int a[125]={0},count[100005];   //数组count用来记录第i个值前面比他大的数目

    scanf("%d",&n);

    for(i=0;i<n;i++){

        scanf("%d",&m);      //先输入一个值 接着跑for循环

        a[m]++;

        count[i]=0;

        for(j=m+1;j<=120;j++){      //从m+1这个数开始 判断这个数的数目是否多余0个

            if(a[j]!=0){                 //如果多于 说明这个数之前出现了几次

                count[i]+=a[j];

            }

        }

    }

    for(i=0;i<n;i++){

        printf("%d ",count[i]);     //对每个i 输出相应的数目count[i]

    }

    printf("\n");

    return 0;

}

总结：

1.代码最后不加\n(换行) 也会判对

2.在输入后面可以做一些事就像打表一样缩短时间

3.根据数据大小先考虑会不会tle

感谢：点击访问他的博客

巴特西

排队I(替换两层复杂for循环、避免TLE)

问题 C: 排队I(点击)

样例输入

思路：

代码：

总结：

最新文章

热门文章