在vector 中 upper_bound的使用

vector的lower_bound和upper_bound
lower_bound:
返回第一个大于等于x的数的位置。
upper_bound:
返回第一个大于x的数的位置。
具体在vector的使用：
插入元素：
v.insert(upper_bound(v.begin(),v.end(),a),a);
在第一个大于a的数的前面插入a;
同样用lower_bound就是大于等于。

P1168 中位数

题目描述
给出一个长度为\(N\)的非负整数序列\(A_i\)，对于所有\(1 ≤ k ≤ (N + 1) / 2\)，输出\(A_1, A_1 \sim A_3, …,A_1 \sim A_{2k - 1}\)的中位数。即前\(1,3,5,…\)个数的中位数。
输入格式
第\(1\)行为一个正整数\(N\)，表示了序列长度。
第\(2\)行包含\(N\)个非负整数\(A_i (A_i ≤ 10^9)\)。
输出格式
共\((N + 1) / 2\)行，第\(i\)行为\(A_1, A_3, …, A_{2k - 1}\)的中位数。
输入

7
1 3 5 7 9 11 6

输出

1
3
5
6

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
vector<int> v;
int n,a;
int main()
{
   cin>>n;
   for(int i=1;i<=n;i++)
   {
       cin>>a;
       v.insert(upper_bound(v.begin(),v.end(),a),a);
       //这样的插入就实现了过程中排序，中位数要求有序。
       if(i % 2 == 1)
       {
           cout<<v[(1+i)/2-1]<<endl;
       }
   }
   return 0;
}

P3871 [TJOI2010]中位数

题目描述
给定一个由N个元素组成的整数序列，现在有两种操作：
1 add a

在该序列的最后添加一个整数a，组成长度为N + 1的整数序列

2 mid
输出当前序列的中位数

中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个）

例1：1 2 13 14 15 16 中位数为13

例2：1 3 5 7 10 11 17 中位数为7

例3：1 1 1 2 3 中位数为1
输入格式
第一行为初始序列长度N。第二行为N个整数，表示整数序列，数字之间用空格分隔。第三行为操作数M，即要进行M次操作。下面为M行，每行输入格式如题意所述。
输出格式
对于每个mid操作输出中位数的值
输入

6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid

输出

5
13

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int N=2e6;
string s;
vector<int> v;
int n,m,a;
int main()
{
   scanf("%d",&n);
   for(int i=1;i<=n;i++)
   {
       scanf("%d",&a);
       v.insert(upper_bound(v.begin(),v.end(),a),a);
   }
   scanf("%d",&m);
   for(int i=1;i<=m;i++)
   {
      cin>>s;
      if(s == "add") 
      {
          scanf("%d",&a);
          v.insert(upper_bound(v.begin(),v.end(),a),a);
      }
      else{
          int len = v.size();
          int mid = (len - 1)>>1;
          //for(int i=0;i<len;i++)
          //printf("%d ",v[i]);
          printf("%d\n",v[mid]);
      }
   }
   return 0;
}