codeforces #333 div 2B. Approximating a Constant Range

2015-12-22 · 2 min read · set stl

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))

/* ***********************************************
Author :111qqz
Created Time :2015年12月22日 星期二 15时10分01秒
File Name :code/cf/#333/B.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int n ;
8int a[N];

 1void ruler()
 2{
 3    int head = 1;
 4    int tail = 1;
 5    int ans = -1;
 6    multiset<int>se;
 7    while (tail<=n)
 8    {
 9	se.insert(a[tail]);
10//	cout<<"tail:"<<tail<<" a[tail]:"<<a[tail]<<" "<<endl;
11//	cout<<"min:"<<*se.begin()<<" max:"<<*se.end()<<endl;
12	if (abs(*se.begin()-*se.rbegin())>1)
13	{
14	    se.erase(se.find(a[head]));//这样写是删除multiset中的一个元素，写成se.erase(a[head])会删除掉所有的。
15					//删掉一个就可以。虽然删掉一个不一定使得满足最大值和最小值差的绝对值小于等于1
16					//但是之前插入一个，现在删除一个，区间长度没有变，就是不会对当前答案有影响。
17	    head++;
18	}
19	ans = max(ans,int(se.size()));

//	cout<<"size:"<<int(se.size())<<"head:"<<head<<" tail:"<<tail<<endl;
	tail++;

1    }
2   cout<<ans<<endl;
3    multiset<int>::iterator it;

 1//    for ( it =se.begin() ;it !=se.end() ;it++)
 2 //   {
 3//	cout<<*it<<endl;
 4//    }
 5}
 6int main()
 7{
 8	#ifndef  ONLINE_JUDGE 
 9	freopen("code/in.txt","r",stdin);
10  #endif

	cin>>n;
	for ( int i = 1 ; i<= n ; i++) scanf("%d",&a[i]);

//	for ( int i = 1 ; i <= n ; i++) printf("%d %d\n",i,a[i]);
	ruler();

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}