登录 注册
无
//只能通过80%,不知什么问题,难道是双重循环导致复杂度太大???
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
while(cin>>n)
vector<int> num(n);
for(int i=0;i<n;i++)
cin>>num[i];
vector<int>res(n,0);
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
if(num[i]<num[j])
res[i]++;
}
for(int i=0;i<n-1;i++)
cout<<res[i]<<" ";
cout<<res[n-1]<<endl;
res.clear();
num.clear();
20w的数据啊。你O(n^2)的复杂度怎么可能过....
http://www.lintcode.com/en/problem/count-of-smaller-number-before-itself/看这道题吧,线段树