lower_bound()和upper_bound

函數lower_bound()在first和last中的前閉後開區間進行二分查找，傳回大于或等于val的第一個元素位置。如果所有元素都小于val，則傳回last的位置,upper_bound()同理，隻是傳回大于val的第一個元素位置。

是以，要記住：函數lower_bound()在first和last中的前閉後開區間進行二分查找，傳回大于或等于val的第一個元素位置。如果所有元素都小于val，則傳回last的位置，且last的位置是越界的！

low_bount()傳回查找元素的第一個可安插位置，也就是“元素值>=查找值”的第一個元素的位置.

普通數組(a[1],a[2]...,a[n])的寫法是：j=upper_bound(a+1,a+1+n,b)-a;j是a[i]數組中第一個大于b的位址符。

另一種情況是如果定義結構體:

struct node{

int id,num;

}a[100006],q[100006];

如果這時用到upper_bound，如對于數字b，傳回結構體a[i].num中第一個大于b的位址符,那麼不能寫成j=upper_bound(a+1,a+1+n,b)-a;

這裡要把輸入的數字存在結構體裡，如上面寫的q[100006],然後重載運算符‘<',比較的時候用j=upper_bound(a+1,a+1+n,p[i])-a;

整體寫法如下：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
struct node{
	int id,num;
}a[100006],q[100006];
/*bool operator <(const node &q,const node &w)
{
	return q.num<w.num;
}兩種寫法都行，但上面這種快*/ 
bool operator<(node a,node b){
	return a.num<b.num;
}

int main()
{
	int n,m,i,j,k;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		map<int,int>hash;
		hash.clear();
		for(i=1;i<=n;i++){
			scanf("%d",&a[i].num);
			a[i].id=i;
			hash[a[i].num]++;
		}
		sort(a+1,a+1+n);
		for(i=1;i<=m;i++){
			scanf("%d",&q[i].num);
			if(hash[q[i].num]==0){
				printf("-1\n");continue;
			}
			else{
				hash[q[i].num]--;
				j=upper_bound(a+1,a+1+n,q[i])-a;
				printf("%d\n",a[j-1].id);
				for(k=j-1;k<=n-1;k++){
					a[k].id=a[k+1].id;
					a[k].num=a[k+1].num;
				}
				n--;
			}
		}
	}
	return 0;
}
           

還有一點，就是運算符定義後，排序時如果不加cmp，那麼就按定義的運算符排序，如果自己再重新寫一個cmp，那麼就按自己寫的來排序。