++ std http lin n) 不同 新建 元素 class
其中只包含一行,为Sherry最少需要的双端队列数。
- 6
- 3 6 0 9 6 3
- 2
100%的数据中N≤200000。
此题手玩了很久,发现了一个对于不重复的元素可行的nlogn的方法。首先给每一个元素编号1~n,然后放在结构体里面sort。例如样例:
IN:6 1 8 7 4 2 6 OUT:3
序号变成了1 5 4 6 3 2。可以发现首先对于1号,左右都没有已经加入队列的元素,那么新建一个ans=1。对于2,新建一个ans=2。对于3,右边有2了,就把3加入到2,ans=2。对于4,新建一个,ans=3。对于5加入到1和4都可以,对于6,加入到4和3都可以。这个可以使用并查集轻松实现。但是题目中的是有重复的。
我们想,对于排好序的元素,每一个单调队列一定都是从中截取连续的一段作为自己的元素的,那么我们观察一下他的序号。例如样例,第一个队列中元素的序号为3 1 6,第二个为5 2 4。题目要求依次考虑,那么初始的元素必定序号最小,然后它左右两边的序号都要比它大,所以这是一个元素单调,元素的序号呈中间小,两边大的单调队列。特别的,序号递增或递减(左边没有元素或右边没有元素)。那么怎么求呢?
第一种不重复元素的方法遇到重复的元素就没有办法了,但是发现了序号的规律之后,我们对于重复的元素,就可以合并了,然后记下相同元素所对应的序号最大与序号最小值即可。当前面一个元素(合并之后,元素是无相同的了)是递增的,那么当前这一个元素如果没有办法继续递增,就要新建一个单调队列了。前面元素递减同理。
不存在一种情况使得相同的元素在不同的单调队列。因为队列起始元素自然递减更优,限制递减状态改为递增的是最小值,把相同元素放在不同的队列,并不能把最小的放过去,还不如放在一起。
- #include<queue>
- #include<cstdio>
- #include<vector>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define RG register
- #define LL long long
- #define fre(a) freopen(a".in","r",stdin);//freopen(a".out","w",stdout);
- using namespace std;
- const int MAXN=210000;
- int n,now,down,up,ans,top;
- int mx[MAXN],mi[MAXN];
- struct ed
- {
- int v,id;
- }a[MAXN];
- bool comp(ed x,ed y)
- {
- if(x.v!=y.v)
- return x.v<y.v;
- return x.id<y.id;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&a[i].v);
- a[i].id=i;
- }
- sort(a+1,a+n+1,comp);
- top++; mi[top]=mx[top]=a[1].id;
- for(int i=2;i<=n;i++)
- {
- if(a[i].v!=a[i-1].v)
- top++ , mi[top]=a[i].id;
- if(a[i].v!=a[i+1].v)
- mx[top]=a[i].id;
- }
- now=mi[1]; down=1; up=0;
- for(int i=2;i<=top;i++)
- {
- if(up)//一个断点
- {
- if(mi[i]<now)
- { ans++; up=0; down=1; now=mi[i]; }
- else
- now=mx[i];
- }
- else if(down)
- {
- if(mx[i]<now)
- now=mi[i];
- else
- up=1,now=mx[i];
- }
- }
- printf("%d\n",ans+1);
- return 0;
- }
BZOJ 2457 [BeiJing2011] 双端队列
来源: http://www.bubuko.com/infodetail-2361916.html