【二分优化】Preparing for Merge Sort CodeForces

【二分优化】Preparing for Merge Sort CodeForces - 847B

Think:
1知识点：二分优化
2题意：输入一个长度最长可达到2e5的序列，序列中的每一个数各不相同，要求按照步骤分组，分组步骤为：
（１）：从左到右在序列中选取第一个未使用的数
（２）：从（１）步找到的数开始向右继续寻找，每次选取一个未使用的且大于前一个被选取的数的数
（３）：若无法进行第（１）步即序列中元素已全部分组，结束分组；
若无法进行第（２）步，进行下一次分组；
3解题思路：
（１）：for循环暴力模拟（一个小组一个小组的选取）——超时
（２）：每次选择序列中的当前元素，试探是否可以放置在之前已经分好的小组，若可以，放置更新，若不可以，开新的小组进行放置——（暴力查询放置小组——超时）——（通过数据查询临界情况优化暴力查询放置小组——1216msAccepted）——（临界情况优化＋二分优化查询放置小组——139msAccepted）

vjudge题目链接

以下为Accepted代码——（通过数据查询临界情况优化暴力查询放置小组——1216msAccepted）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> v1[204014];
vector <int>:: iterator it;
int rec[204014];
int main(){
    int n, i, j, k, t;
    scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d", &rec[i]);
        k = 0;
        v1[k++].push_back(rec[0]);
        for(i = 1; i < n; i++){
            if(k > 0){
                t = v1[k-1].back();
                if(t > rec[i]){
                    v1[k].push_back(rec[i]);
                    k++;
                    continue;
                }
            }
            for(j = 0; j < k; j++){
                t = v1[j].back();
                if(t < rec[i]){
                    v1[j].push_back(rec[i]);
                    break;
                }
            }
        }
        for(i = 0; i < k; i++){
            for(it = v1[i].begin(); it != v1[i].end(); it++){
                if(it != v1[i].begin()) printf(" ");
                printf("%d", *it);
            }
            printf("\n");
        }
    return 0;
}

以下为Accepted代码——（临界情况优化＋二分优化查询放置小组——139msAccepted）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
    int x;
    int id;
    bool operator < (const Node &b) const{
        if(id == b.id) return x < b.x;
        return id < b.id;
    }
}rec[204014];
int grou[204014];
int main(){
    int n, i, k, l, r, mid;
    while(~scanf("%d", &n)){
        for(i = 0; i < n; i++){
            scanf("%d", &rec[i].x);
        }
        k = 0;
        grou[k++] = rec[0].x;
        rec[0].id = 0;
        for(i = 1; i < n; i++){
            if(grou[k-1] > rec[i].x){
                grou[k++] = rec[i].x;
                rec[i].id = k-1;
                continue;
            }
            l = 0, r = k-1;
            while(l <= r){
                mid = (l+r)>>1;
                if(mid == 0 && grou[mid] < rec[i].x){
                    grou[mid] = rec[i].x;
                    rec[i].id = mid;
                    break;
                }
                else if(mid > 0 && grou[mid] < rec[i].x && grou[mid-1] > rec[i].x){
                    grou[mid] = rec[i].x;
                    rec[i].id = mid;
                    break;
                }
                else if(grou[mid] > rec[i].x){
                    l = mid+1;
                }
                else if(mid > 0 && grou[mid-1] < rec[i].x){
                    r = mid-1;
                }
            }
        }
        sort(rec, rec+n);
        for(i = 0; i < n; i++){
            printf("%d", rec[i].x);
            if(i == n-1 || rec[i].id < rec[i+1].id) printf("\n");
            else printf(" ");
        }
    }
    return 0;
}