题目描述
未来某一天,Miaowu回首曾经,发现自己已度过的n年里,每一年都在为黑暗世界做贡献,第i年为黑暗世界的贡献值是a[i].理论上来说,一只猫所坐的贡献应该是i>j则a[i]>a[j],但Miaowu却惊奇的发现,自己那曾经的岁月里,竟然有ia[j],的出现,这一下就勾起了他的兴趣,他想知道,这n年里,有多少个相应的两年自己所做的贡献是正常的,也就是说有多少对i,j满足i<j且a[i]<a[j].这应该是个很简单的问题,直接数就行了,但不幸的是,Miaowu已经老了(n很大很大),没有年轻时的激情了,所以想请你帮忙,Miaowu会告诉你他这n年每年的所做的贡献值,并且这些年的所做的贡献均是[1,n]之间的数,而且没有重复,然后你需要做的就是告诉他有多少对符合条件的年份.
输入
输入多组数据,每组数据包含两行,第一行一个整数n,表示他已活了n年,第二行有n个整数,第i个数a[i]表示他第i年所做的贡献值,
数据范围: 1 <= n <= 200000, 1<= a[i] <=n
这里我用的是线性查找数组的方法，提交网站时显示时间超限，想问一下大佬们怎么降低遍历数组复杂度，
#include
#include
#include
#define M 200000
int main()
{
int a[M]={0};
int n=0,i,j;
while(scanf("%d",&n)!=EOF)
{
int long t=0;
double x;
for(i=0;i
{
scanf("%d",&a[i]);
}
for(i=n;i>0;i--)
{
for(j=i;j>0;j--)
{
if(a[i]>a[j-1]) t++;
}
}
x=pow(10,7);
printf("%lf",x);
x=x+9;
fmod(t,x);
printf("%d",t);
printf("\n");
memset(a,0,sizeof(a));
}
return 0;
}
