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
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;
}
本番中にいろいろ作って試したけどどっかいった