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

「爱情、让人受尽委屈。」 2022-06-05 11:47 88阅读 0赞

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

[vjudge题目链接][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;
    }

[vjudge]: https://vjudge.net/problem/CodeForces-847B