BZOJ – 2457 思維+貪心

//為什麼我的Chrome OS更新後變成強制繁體了??

題目要求使用最少的雙端隊列來維護一個單調非降序列

先來看下規律

首先,val肯定是單調非降的,在相等val範圍內的id可以xjb亂放不影響

其次,在單調可解的val範圍內,id一定是中間小兩邊大(中間是最初維護的,而兩邊是不斷地插入肯定越來越大)

即id在某一範圍內是v型分布的

因為val是單調的,所以對不同的val進行分塊管理對應的id,很顯然最低成立的條件是相同val(塊)的id肯定是緊挨著的,而且是每一個塊逐步往右靠(單調嘛)

如果不可解,那就意味著id的分布至少是vv型的,即至少多了一個極大值拐點,那麼拐點數+1就是使用隊列的數量

所以問題轉換成給定你未管理好的id,求最少的拐點數

貪心策略是能相同單調性就盡可能相同單調,否則相反單調

(一個錯誤策略是盡可能遞減單調,因為當前遞減的話對應三種不同高度的右下""塊狀id是最優的,然而GG,原因待查)

/*H E A D*/
struct A{
    int id,val;
}a[maxn];
bool cmp(A a,A b){
    if(a.val!=b.val)return a.val<b.val;
    return a.id<b.id;
}
int main(){
    int n;
    while(~iin(n)){
        rep(i,1,n){
            a[i].val=read();
            a[i].id=i;
        }
        sort(a+1,a+1+n,cmp);
        vector<A> block[maxn];
        int now=0;
        rep(i,1,n){
            if(i==1||a[i].val!=block[now][0].val){
                now++;
                block[now].push_back(a[i]);
            }else{
                block[now].push_back(a[i]);
            }
        }
        int ans=0;
        rep(i,1,now) sort(block[i].begin(),block[i].end(),cmp);//trend=+1
        vector<int> que;
        int trend;
        rep(i,1,now){
            if(i==1){
                for(int j = block[i].size()-1; j >= 0; j--){
                        que.push_back(block[i][j].id);
                }
                trend=-1;
            }else if(trend==-1){
                if(block[i].back().id<que.back()){
                    for(int j = block[i].size()-1; j >= 0; j--){
                        que.push_back(block[i][j].id);
                    }
                    trend=-1;
                }else{
                    for(int j = 0; j < block[i].size(); j++){
                        que.push_back(block[i][j].id);
                    }
                    trend=1;
                }
            }else{
                if(block[i][0].id>que.back()){
                    for(int j = 0; j < block[i].size(); j++){
                        que.push_back(block[i][j].id);
                    }
                    trend=1;
                }
                else{
                     for(int j = block[i].size()-1; j >= 0; j--){
                        que.push_back(block[i][j].id);
                    }
                    trend=-1;
                    ans++;
                }
            }
        }
        println((ans+1));
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注