赛氪|人物风云榜|c语言-爱代码爱编程
问题描述及输入输出如下图:
数据范围:
初步思路:
定义两个数组,a[]用来装输入的值,b[]用来装排序的值
定义一个变量top=1,即每个数起初排序值都为1
在两层for循环中比较a[i]的值,每次第二层for开始前都要把top的值变为1
比较结果是小于,top值+1;大于或等于的情况下,top的值不改变;每次比较结束都把top的值传给对应的b[i]里
初代码:
#include<stdio.h>
int main()
{
int n,i,j,top;
int a[100100];
int b[100100];
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
{
top=1;
for(j=1;j<=n;j++)
{
if(a[i]<a[j]) {top++; b[i]=top;}
else b[i]=top;
}
}
for(i=1;i<=n;i++)
printf("%d ",b[i]);
printf("\n");
return 0;
}
结果前6个通过,后面4个Time Limit Exceeded,超出时间限制,没有通过。
思考原因,应该是两层for循环在数据量加大后花费的时间太多了,超过了题目要求。
考虑用函数解决问题,舍弃b[]数组,初次修改如下:
#include<stdio.h>
int n,i,j;
int a[100100];
int s(int x)
{
int top=1;
for(i=1;i<=n;i++)
{
if(x<a[i]) top=top+1;
else top=top;
}
return top;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(j=1;j<=n;j++)
printf("%d ",s(a[j]));
printf("\n");
return 0;
}
结果只是比第一次多了一个正确。。。思考ing虽然用了函数,速度提升了一丢丢,但本质上还是用了两个循环,所以时间成本依旧很高。
皱眉思考,在庞大数据下每个a[i]都要重复地相互比较,确实会有很大的浪费,有没有什么办法在两个数比较之后就不再重复比较,并且小的那个数top+1,而大的那个数top保持不变呢?
可恶,想不出来,先放着吧,,,优化代码好难。。。
如果哪位大佬看到此篇文章,那就是咱们的缘分!
请求大佬支援————哭/(ㄒoㄒ)/~~