hiho 1572

小Hi家的阳台上摆着一排N个空花盆，编号1~N。从第一天开始，小Hi每天会选择其中一个还空着花盆，栽种一株月季花，直到N个花盆都栽种满月季。

我们知道小Hi每天选择的花盆的编号依次是A₁, A₂, ... A_N。随着花盆中被栽种上月季，连续的空花盆数量越来越少。

现在小Ho想知道，第一次出现恰好K个连续空花盆（恰好是指这K个空花盆两边相邻的位置都不是空花盆）是第几天？

假设N=7，K=2，小Hi第1天~第7天选择的花盆编号依次是：4、2、7、5、1、3、6。

1234567
OOOOOOO 第0天，一段7个连续空花盆  
OOOXOOO 第1天，一段3个连续空花盆，和另一段3连续个空花盆  
OXOXOOO 第2天，1个、1个和3个连续空花盆  
OXOXOOX 第3天，第一次出现2个连续空花盆  
 ....

输入

第一行包含两个整数，N和K。

第二行包含N个两两不同的整数，A₁, A₂, ... A_N。

对于30%的数据， 1 <= K < N <= 1000

对于100%的数据，1 <= K < N <= 100000， 1 <= A_i <= N

输出

输出第一次出现恰好连续K个空花盆是第几天。如果自始至终没出现输出-1

--------------------------------------------------------------------------------------------------------------------------

维护一个有序列表，每insert一个数则找到比它稍大和稍小的数，查看这两个区间长度是否满足条件。

我写了个二叉排序树超时了。。

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))
#define MIN(a,b) ((a)<=(b)?(a):(b))
#define OO 0x0fffffff
using namespace std;
typedef long long LL;

struct Node{
    int data;
    Node *left,*right,*father;
    Node(){left=right=father=NULL;}
    Node(int data,Node* father):data(data),father(father){
        left=right=NULL;
    }
    Node* insert(int newd,int& bigger,int& smaller){
        if(newd<data){
            bigger = data;
            if(left==NULL) return (left = new Node(newd,this));
            else return left->insert(newd,bigger,smaller);
        }
        else{
            smaller = data;
            if(right==NULL) return right = new Node(newd,this);
            else return right->insert(newd,bigger,smaller);
        }
    }
};

int main(){
    int bigger,smaller;
    int N,K,data; cin>>N>>K; K++;
    Node* root = new Node(0,NULL);
    root->insert(N+1,bigger,smaller);

    int ans = -2;
    bool finded = false;
    for(int i=0;i<N;i++){
        scanf("%d",&data);
        if(finded) continue;

        Node* p = root->insert(data,bigger,smaller);
        //int bigger = p->findBigger();
        //int smaller = p->findSmaller();
        if(bigger-data==K||data-smaller==K){
            ans = i; finded = true;
        }
    }
    printf("%d
",ans+1);
    return 0;
}

看了别人代码才知道有upper_bound这个东西，直接调用就行了。。。

ac的代码

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))
#define MIN(a,b) ((a)<=(b)?(a):(b))
#define OO 0x0fffffff
using namespace std;
typedef long long LL;

set<int> sets;

int main(){
    int N,K,data; cin>>N>>K; K++;
    sets.insert(0); sets.insert(N+1);

    int ans = -2;
    bool finded = false;
    for(int i=0;i<N;i++){
        scanf("%d",&data);
        if(finded) continue;
        auto iter = sets.upper_bound(data);
        int bigger = (*iter);
        int smaller = *(--iter);
        if(bigger-data==K||data-smaller==K){
            finded = true, ans = i;
        }
        sets.insert(data);
    }
    printf("%d
",ans+1);
    return 0;
}