Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/contest/602/problem/B 题意：给定n个数，问最大连续区间长度，满足这段区间内最大值和最小值的差的绝对值小于等于1. 思路：尺取+set。尺取法，由于要时刻得到一段区间的最大值和最小值，而且可能有重复元素，所以用multiset.
需要注意的是，set里最小值是se.begin() ，最大值是se.rbegin()这样比较好。。不要用se.end()之类。。。
另一个需要注意的是，multiset里用erase的时候。如果se.erase(x)会把集合里所有的x都删除掉。如果指向删除一个，那么应该写成se.erase(se.find(x))
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月22日 星期二 15时10分01秒
4File Name :code/cf/#333/B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n ;
35int a[N];
36
37void ruler()
38{
39 int head = 1;
40 int tail = 1;
41 int ans = -1;
42 multiset<int>se;
43 while (tail<=n)
44 {
45 se.insert(a[tail]);
46// cout<<"tail:"<<tail<<" a[tail]:"<<a[tail]<<" "<<endl;
47// cout<<"min:"<<*se.begin()<<" max:"<<*se.end()<<endl;
48 if (abs(*se.begin()-*se.rbegin())>1)
49 {
50 se.erase(se.find(a[head]));//这样写是删除multiset中的一个元素，写成se.erase(a[head])会删除掉所有的。
51 //删掉一个就可以。虽然删掉一个不一定使得满足最大值和最小值差的绝对值小于等于1
52 //但是之前插入一个，现在删除一个，区间长度没有变，就是不会对当前答案有影响。
53 head++;
54 }
55 ans = max(ans,int(se.size()));
56
57// cout<<"size:"<<int(se.size())<<"head:"<<head<<" tail:"<<tail<<endl;
58 tail++;
59
60 }
61 cout<<ans<<endl;
62 multiset<int>::iterator it;
63
64// for ( it =se.begin() ;it !=se.end() ;it++)
65 // {
66// cout<<*it<<endl;
67// }
68}
69int main()
70{
71 #ifndef ONLINE_JUDGE
72 freopen("code/in.txt","r",stdin);
73 #endif
74
75 cin>>n;
76 for ( int i = 1 ; i<= n ; i++) scanf("%d",&a[i]);
77
78// for ( int i = 1 ; i <= n ; i++) printf("%d %d\n",i,a[i]);
79 ruler();
80
81 #ifndef ONLINE_JUDGE
82 fclose(stdin);
83 #endif
84 return 0;
85}