数组
Time Limit: 2000/1000ms (Java/Others)
Problem Description:
给一个数组a[n],令s[i]为数组a中比a[i]大的数的个数。求数组s。
Sample Input:
5
3 4 5 1 2
10
11 4 12 5 3 8 10 6 7 9
Sample Output:
2 1 0 4 3
1 8 0 7 9 4 2 6 5 3
解题思路:简单的二分查找,水过!upper_bound(b,b+n,a[i])-b返回的是大于a[i]的第一个元素的下标。二分查找的时间复杂度是O(log(n)),所以总的时间复杂度大约为O(nlog(n))。
AC代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=1e5+5;
4 int n,a[maxn],b[maxn],s[maxn];
5 int main(){
6 while(~scanf("%d",&n)){
7 for(int i=0;i<n;++i){scanf("%d",&a[i]);b[i]=a[i];}
8 sort(b,b+n);//先排序
9 for(int i=0;i<n;++i)
10 s[i]=n-(upper_bound(b,b+n,a[i])-b);//二分查找
11 for(int i=0;i<n;++i)
12 printf("%d%c",s[i],i==n-1?'
':' ');
13 }
14 return 0;
15 }