每日一题：订单编号

订单编号 - 题目 - Daimayuan Online Judge

一开始想用二分答案的，但是后来发现不行，二分答案每找到一个值，就要去掉它的左半边或右半边，但是这里不能去 

 错误代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e7;
int a[N];
int n;
bool flag[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int max1 = a[1];
    for (int i = 1; i <= n; i++) {
        int l = a[i], r = max1 + 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (!flag[mid]) r = mid;
            else l = mid + 1;
        }
        flag[l] = true;
        a[i] = l;
        max1 = max(max1, l);
    }
    for (int i = 1; i <= n; i++) cout << a[i]<<" ";
    return 0;
}

 该题可以用set容器，用pair表示区间，将区间插入set表示该区间里的数是没有用过的，而当哪一个数用过后，就将该数从set中删去，具体删去数的做法是将原有区间删去，插入新的区间来使该数不在新的区间中

 分块解释代码：

inline void insert(int l, int r) {
    if (l > r) return;
    s.insert(make_pair(r, l));
}

 这样一来，区间是按照右端点从小到大排序的

auto it = s.lower_bound(make_pair(x, 0));

 AC代码(用cin,cout会超时)：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
set<pair<int,int>>s;
int n;
inline void insert(int l, int r) {
    if (l > r) return;
    s.insert(make_pair(r, l));
}
int main()
{
    scanf("%d", &n);
    s.insert(make_pair(2e9, 1));//一开始区间是1到2e9,表示这些数都没用过
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        auto it = s.lower_bound(make_pair(x, 0));//找到右端点大于等于x的最近的一个区间
        int l = it->second,r = it->first;
        //x在区间中，那么编号x还未用过，就用原来的编号x
        if (l <= x) {
            printf("%d ", x);
            insert(l, x - 1);
            insert(x + 1, r);
            s.erase(it);
        }
        //x不在区间中，编号x已经用过了，得找大于等于x的且没用过的编号,即离它最近的下一个区间的左端点l
        else {
            printf("%d ", l);
            insert(l + 1, r);
            s.erase(it);
        }
    }
    return 0;
}