vijos P1062 迎春舞会之交谊舞
来源：程序员人生 发布时间：2015-05-15 07:48:11 阅读次数：3354次
这题被归类为栈，所以用栈来做咯；
整体思想还是括号匹配，不过关键在于如何求出相互匹配的两人中夹杂着多少个男生，我的方法是定义结构体记录每一个人左侧男生的个数
#include<iostream>
#include<stack>
#define maxn 1500+5
using namespace std;
struct stu
{
int a,sex;//a位，该人（不管男女）左侧男生的个数，sex为该人的性别；
};
stack<stu>root;
int f[maxn];//读入数据的贮存
int g[maxn];// 记录第i个女生与她前1个女生之间夹着多少个男生；
int re[maxn];//记录结果
int main()
{
int n;
while(cin>>n)
{
f[0]=0;
for(int i=1;i<=n;i++) cin>>f[i];
for(int i=1;i<=n;i++) g[i]=f[i]-f[i⑴];
while(root.size()) root.pop();//清空
int sum=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<g[i];j++)
{
stu x;
x.a=sum;
x.sex=1;
root.push(x);
sum++;
}
re[i]=sum-root.top().a;
root.pop();
}
cout<<re[1];
for(int i=2;i<=n;i++) cout<<" "<<re[i];
cout<<endl;
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
