Codeforces#333 Div2 B問題

はじめに

Codeforces Round #333 Div. 2 Prob. B. Approximating a Constant Range

問題:http://codeforces.com/contest/602/problem/B

与えられた数列で、minとmaxの差が1になる区間の最大サイズを求める。

解けたけど効率悪い実装していたので書いておく。

考え方

multisetに数字を突っ込んだり削除したりしながらしゃくとりするだけ。計算量はO(nlogn)

ACしたけどmultisetの挙動がよくわからず40分ぐらいかかった。→http://codeforces.com/contest/602/submission/14450953

  • eraseは値を指定すると重複しているものすべて消去。一個消去ならfindしたiteratorを指定する。
  • 最大値や最小値を取り出すのはrbeginやbeginを使うと楽。(なんとか_boundを使うよりバグりにくい)
  • multiset<int,greater<int>>みたいに宣言すると大きい順に並ぶようにできる

set、multiset、map、multimap、dequeなどは良く忘れるのでまとめた記事を書きたい。

解答

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }

    multiset<int> nums; //lからrまでの数列の集合が入る
    int ret = 0,l=0;

    for(int r = 0; r < n; ++r){
        nums.insert(a[r]);
        int max_num = *nums.rbegin(); //これでmultisetやsetに入った数字の最大値がとれる
        int min_num = *nums.begin();  //これで最小値
        while(1<max_num-min_num){
            nums.erase(nums.find(a[l])); //multisetでnum.erase(a[l])とやると
                                         //a[l]と等しいものがすべてeraseされる
            l++;
            max_num = *nums.rbegin();
            min_num = *nums.begin();
        }
        ret = max(ret,r-l+1);
    }

    cout << ret << endl;
    return 0;
}

テストケース

本番中にいろいろ作って試したけどどっかいった