给一个数组a[n]，令s[i]为数组a中比a[i]大的数的个数。求数组s。
输入包含多组测试数据，对于每组数据，输入一个整数n（1<=n<=10^5)，接下来有n个整数a[i](0<=a[i]<=10^9);保证输入的a[i]全部不同。
对于每组数据，输出数组s。
5 3 4 5 1 2 10 11 4 12 5 3 8 10 6 7 9
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?‘\n‘:‘ ‘); 13 } 14 return 0; 15 }
原文：https://www.cnblogs.com/acgoto/p/9216554.html