小组队列
思路
我们可以建两个队列，一个存小组编号的顺序，一个存各个小组的顺序。每有一个新小组的人入队，将他小组编号也入队
代码
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
int n,idx=0,idx2=0;
while(cin>>n&&n)
{
queue<int> gn,group[1010];
unordered_map<int,int> grouph;
idx2=0;
for(int i=1;i<=n;i++)
{
int size1;
cin>>size1;
for(int j=1;j<=size1;j++)
{
int x;
cin>>x;
grouph[x]=i;
}
}
string op;
int x;
while(1)
{
cin>>op;
if(op=="STOP") break;
if(op=="ENQUEUE")
{
cin>>x;
group[grouph[x]].push(x);
if(group[grouph[x]].size()==1) gn.push(grouph[x]);
}
else
{
int num=group[gn.front()].front();
group[gn.front()].pop();
if(group[gn.front()].size()==0) gn.pop();
a[++idx2]=num;
}
}
cout<<"Scenario #"<<++idx<<endl;
for(int i=1;i<=idx2;i++) cout<<a[i]<<endl;
cout<<endl;
}
}
CSP-S 2016 Day2 T2 蚯蚓
思路
代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,q,u,v,t,a[100010],b[7000010],c[7100010],idxb,idxc;
queue<long long> x,l,r;
long long get_max()
{
long long maxx=-1000000000;
if(x.size()) maxx=max(maxx,x.front());
if(l.size()) maxx=max(maxx,l.front());
if(r.size()) maxx=max(maxx,r.front());
if(maxx==x.front()&&x.size()) x.pop();
else if(maxx==l.front()&&l.size()) l.pop();
else if(r.size())r.pop();
return maxx;
}
bool cmp(long long a,long long b)
{
return a>b;
}
void len()
{
while(x.size()||l.size()||r.size()) c[++idxc]=get_max();
return;
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+n+1);
for(int i=n;i>=1;i--) x.push(a[i]);
long long delta=0;
for(int i=1;i<=m;i++)
{
long long maxx=get_max()+delta;
if(!(i%t)) b[++idxb]=maxx;
long long lx=maxx*1.0*u*1.0/v,rx=maxx-lx;
lx-=delta+q;
rx-=delta+q;
l.push(lx);
r.push(rx);
delta+=q;
}
len();
for(int i=1;i<=idxb;i++) printf("%lld ",b[i]);
cout<<endl;
for(int i=1;i<=idxc;i++) if(!(i%t)) printf("%lld ",c[i]+delta);
}
双端队列
思路
我们先排序,
代码
#include<bits/stdc++.h>
using namespace std;
pair<int,int> a[200010],b[200010];
int c[200010],sum=0;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].first;
a[i].second=i;
}
sort(a+1,a+1+n);
int idx=0;
for(int i=1;i<=n;i++)
{
if(i==1)
{
b[++idx].first=a[i].second;
}
if(a[i].first!=a[i-1].first)
{
b[idx].second=a[i-1].second;
b[++idx].first=a[i].second;
}
}
b[idx].second=a[n].second;
int size=0,dzj=1;
for(int i=1;i<=idx;i++)
{
if(b[i].first==b[i].second)
{
c[++size]=b[i].first;
if(i==1) continue;
if(c[size-1]<c[size]&&dzj) dzj=0;
else if(c[size-1]>c[size]&&!dzj)
{
dzj=1;
sum++;
}
}
else if(i==1)
{
c[++size]=max(b[i].first,b[i].second);
c[++size]=min(b[i].first,b[i].second);
}
else
{
if(dzj)
{
if(c[size]>max(b[i].first,b[i].second))
{
c[++size]=max(b[i].first,b[i].second);
c[++size]=min(b[i].first,b[i].second);
}
else
{
c[++size]=min(b[i].first,b[i].second);
c[++size]=max(b[i].first,b[i].second);
dzj=0;
}
}
else
{
if(c[size]<min(b[i].first,b[i].second))
{
c[++size]=min(b[i].first,b[i].second);
c[++size]=max(b[i].first,b[i].second);
}
else
{
c[++size]=max(b[i].first,b[i].second);
c[++size]=min(b[i].first,b[i].second);
sum++;
dzj=1;
}
}
}
}
cout<<sum;
}
最大子序和
思路 先前缀和,我们计算从i到j的和是,越小.越大.
这样我们可以用单调队列维护一个的递减序列，在取最大值
代码
#include<bits/stdc++.h>
using namespace std;
int a[300010],s[300010],q[300010],hh=1,tt=1;
int main()
{
int n,m,maxx=-2e9;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
q[1]=0;
for(int i=1;i<=n;i++)
{
while(i-q[tt]>m&&tt<=hh) tt++;
maxx=max(maxx,s[i]-s[q[tt]]);
while(s[i]<s[q[hh]]&&tt<=hh) hh--;
q[++hh]=i;
}
cout<<maxx;
}
滑动窗口
思路
模板题
代码
#include<bits/stdc++.h>
using namespace std;
int a[1000010],q[1000010],hh,tt=-1;
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
while(hh<=tt&&i-k+1>q[hh]) hh++;
while(hh<=tt&&a[q[tt]]>=a[i])tt--;
q[++tt]=i;
if(i-k+1>=0) cout<<a[q[hh]]<<" ";
}
cout<<endl;
hh=0,tt=-1;
for(int i=0;i<n;i++)
{
while(hh<=tt&&i-k+1>q[hh]) hh++;
while(hh<=tt&&a[q[tt]]<=a[i])tt--;
q[++tt]=i;
if(i-k+1>=0) cout<<a[q[hh]]<<" ";
}
}
