/*
先解释一下样例
6
4 5 6 6 6 6
1 1 1 4 5 6
男 男 男 男 女 男 女 男 女 女 女 女
这道题常规做法可以用栈做，模拟一下即可了
但是其实有更加简单方便的做法
首先我们要弄清楚这个关系
对于一个女生，她的男舞伴的位置满足：
从左向右考虑女生，并从女生位置向左扫描，当扫到第一个未被匹配的男生时
则必然有该男生就是该女生的男舞伴
接下来我们给出证明：
    由题意可知，对于每一对舞伴之间，要么没有人，要么有成对的舞伴。那么我们
对于第一个扫描到的男生，如果不是当前女生的舞伴，那么必然是当前女生右边的某个
女生的舞伴，则中间会有一个单身狗233>3<易知不可能成立
所以我们可以利用这个性质直接乱推一下过去
a[i]表示第i个女生和i-1中间的未匹配男生数
k用来找合适的男生位置，即从女生位置右向走，知道找到一个a[i]到a[i-1]还有未匹配男生位置的地方
则可以匹配上去，距离为i-k+1(要包括该男生)
注意匹配完后a[k]--,即匹配掉了一个男生，数量减1
这样就解决了这道题
                                                    Powder
*/
#include <cstdio>
#include <iostream>
using namespace std;

const int maxn=2000;
int a[maxn];
int n;
int t1,t2;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)//对于每输入一个i都可直接计算出来
    {
        cin>>t1;//输入个数(注意包括了自己的男性舞伴)
        a[i]=t1-t2;//相邻两个的差值(未匹配男生数)
        t2=t1;//更新
        int k=i;//从该女生位置开始找
        while(!a[k])//找有未匹配男生的位置匹配其左边第一个~
            k--;
        cout<<i-k+1<<" ";//包括自己的男生舞伴~
        a[k]--;//匹配掉了一个
    }
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    stack<int> st;
    int a[n];
    cin >> a[0];
    for (int i = 0; i < a[0] - 1; i++)
        st.push(i);
    cout << 1;
    for (int i = 1; i < n; i++) {
        cin >> a[i];
        for (int j = a[i - 1]; j < a[i]; j++)
            st.push(j);
        int top = st.top();
        st.pop();
        cout << " " << a[i] - top;
    }
    cout << endl;
    return 0;
}

//男 男 男 男 女 男 女 男 女 女 女 女
//1  2  3 4  5  6  7 8  9 10 11 12
//可以发现女生位置为: i + wo; 其中1<= i <= n,为输入的次序，wo 为输入的值
#include <iostream>             //迎春舞会之交谊舞
#include <algorithm>
#include <cstdlib>
using namespace std;
const int MaxN = 3005;

int n;
struct Stack {
    int data[MaxN];
    int Top;            
};

void Push(Stack* S, int x)          //入栈
{
    if (S->Top < MaxN)
        S->data[++S->Top] = x;
}

int Pop(Stack* S)                   //出栈
{
    if (S->Top >= 0)
        return S->data[S->Top--];
    else
        return -1;  //栈空
}


int main()
{
    Stack* S = new Stack{ 0 };                      //申请空间, 并初始化
    //Stack* S = (Stack*)calloc(1, sizeof(Stack));  //C语言写法
    S->Top = -1;
    cin >> n;
    int k = 1;
    int wo;
    for (int i = 1; i <= n; i++)
    {
        cin >> wo;
        for (; k < i + wo; k++)     //wo + i就是当前输入的女生位置
            Push(S, k);             //栈存入的是男生位置, 如样例中: 1,2,3,4,6,8
        k++;
        if(i == 1)
            printf("%d", (1 + wo + i - Pop(S)) / 2);        //求距离: 注意一对舞伴算1个距离
        else
            printf(" %d", (1 + wo + i - Pop(S)) / 2);
    }

    delete S;
    system("pause");
    return 0;
}

WA两次。。。忘了删freopen我也是。。。。。。。。
具体，模拟见代码。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000;
int a[maxn],n,t1=0,t2=0,s[maxn],m[maxn],b[maxn];
int main()
{
cin >> n;
for (int i = 1;i<=n;i++){
int ss=0;
cin >> a[i];
b[i+1] = a[i];
a[i] = t2+a[i]-b[i]+1;//重点，要自己推一遍总人数的排列；
t2 = a[i];
m[t2] = 1;
for (int j = t2; j>=1; --j){
if(m[j]==1)
ss++;//记录间隔中女生；
if(!m[j]){
s[i] = t2-j-ss+1;//这个加一不是男生（男生已在问题代码中处理掉）而是本来T2中的女生
m[j] = 2;
break;
}
}
}
for (int i = 1;i<=n;i++)
cout << s[i]<<" ";
return 0;
}

\(\rule{10000000mm}{100000000mm}\)

纯模拟
看到大神们的代码感觉自己Low爆了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<iostream>
using namespace std;
int n,kt=1,cnt[1505],ans[1505],pos=0;
stack<char> p;
stack<int> k;
int main(){
    scanf("%d",&n);
    cnt[0] = 0;
    for(int i=1;i<=n;i++){
        scanf("%d",cnt+i);
        for(int j=cnt[i-1];j<cnt[i];j++){
            p.push('(');
        }
        if(cnt[i-1]==cnt[i]&&p.top()!='|') p.pop(),ans[pos++]=++kt;
        else if(cnt[i-1]!=cnt[i]){
            p.pop();
            p.push('|');
            k.push(kt);
            kt = 1;
            ans[pos++]=kt;
        }
        else{
            while(p.top()=='|'){
                p.pop();
                kt += k.top(); k.pop();
            }
            p.pop();
            p.push('|');
            k.push(kt);
            ans[pos++]=kt;
            kt = 1;
        }
    }

    for(int i=0;i<n-1;i++) printf("%d ",ans[i]);
    printf("%d",ans[n-1]);
    return 0;
}

****不用栈模拟，对于一个女孩纸，她的舞伴只能在左边，所以从当前位置往前找到一个没有访问到的一个就是她的舞伴，借助于女孩纸数组我们可以虚构出一个男孩纸数组，直接for就可以****

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10000
using namespace std;
int n;
int a[N],ans[N];
bool vis[N];
int main()
{
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
                scanf("%d",&a[i]);
                for(int j=a[i];j>=1;--j)
                if(!vis[j]){
                        ans[i]=a[i]-j+1;
                        vis[j]=true;break;
                }
        }
        for(int i=1;i<=n;++i) printf("%d ",ans[i]);
        return 0;
}

模拟栈

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <cmath>
# define R register
# define LL long long

using namespace std;

int n,top,st[5010],a[5010];

template <typename T> inline void in(R T& a){
    R char c=getchar();R int x=0,f=1;
    while (!isdigit(c)){if(c == '-') f=-1; c=getchar();}
    while (isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c = getchar();
    a=x*f;
}

int main(){
    in(n);
    for(R int i=1; i<=n; ++i) in(a[i]);
    R int t=1;
    for(R int i=1; i<=n; ++i)
    {
        while(t<a[i]) st[++top]=t++;
        printf("%d ",a[i]-st[top--]);
    }
}

//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <deque>
#include <cstring>

using namespace std;

int main() {
int n = 0;
scanf("%d", &n);
int dis[1501];
memset(dis, 0, sizeof(dis));
deque<int> ans;
int val = 0, record = 0;
for(int i=0;i<n;++i){
scanf("%d", &val);
if (val > record) {
for (int j = 0; j < val - record; ++j)ans.push_back(0);
record = val;
}
for (auto &k : ans)k++;
dis[i] = ans.back();
ans.pop_back();
}
for (int i = 0; i < n; ++i)printf("%d ", dis[i]);
printf("\n");
//system("pause");
return 0;
}

果然还是stack不熟啊。。写的很懵

#include<iostream>
#include<stack>
using namespace std;
int girl[1503];
stack<int>boy;
int main(void){
    int i,n,index=0;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>girl[i];
    }
    for(int i=0;i<n;i++){
        for(;index<girl[i];index++){
            boy.push(index);
        }
        cout<<girl[i]-boy.top()<<' ';
        boy.pop();
    }
}

按顺序处理每一个女生时，最近的那个未被匹配的男生一定是她的舞伴

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int maxN = 1505;

stack<int> stk;

int main()
{
    int N; scanf("%d", &N);
    int last = 0;
    int cur;
    for(int i=1; i<=N; i++)
    {
        scanf("%d", &cur);
        for(;last<=cur; last++)
            stk.push(i);
        int pos = stk.top();
        stk.pop();
        printf("%d ", i - pos + 1);
    }
    return 0;
}

#include <cstdio>
#include <stack>
int a[2000];

std::stack <int> s;

int main()
{
    int n;
    scanf("%d",&n);
    scanf("%d",&a[0]);
    for (int i = 0; i < a[0]; i++) s.push(i); 
    int x = s.top();
    s.pop();
    printf("%d",a[0] - x);
    for (int i = 1; i < n; i++)
    {
        scanf("%d",&a[i]);
        for (int j = a[i - 1]; j < a[i]; j++) s.push(j);
        int x = s.top();
        s.pop();
        printf(" %d",a[i] - x);
    }
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;


int main()
{
    int n;
    int a[10000];
    scanf("%d", &n);
    int nown;
    int i;
    int m;
    scanf("%d", &m);
    memset(a, 0, sizeof(a));
    for (i = 1;i <= m;i++)
        a[i] = 0;
    a[i] = 1;
    int j;
    nown = i + 1;
    int m1 = m;
    for (i = 2;i <= n;i++)
    {
        scanf("%d", &m);
        for (j = nown;j <= nown + m - m1-1;j++)
            a[j] = 0;
        a[j] = 1;
        m1 = m;
        nown = j+1;
    }

    for (i = 1;i <=nown;i++)
    {
        if (a[i] == 1)
        {
            int ans = 0;
            j = i;
            while (a[j] != 0)
            {
                --j;
                if (a[j] == 3)++ans;
            }
            ++ans;
            printf("%d ", ans);
            a[i] = 2;
            a[j] = 3;
        }
    }

    system("pause");

    return 0;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

const int N = 2000;

int n, a[N], num[N];

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
num[i] = a[i] - a[i - 1];
}
for (int i = 1; i <= n; i++)
for (int j = i; j; j--)
if (num[j]) {
printf("%d ", a[i] - a[j - 1] - num[j] + 1);
num[j]--;
break;
}
return 0;
}

#include<cstdio>
#include<iostream>
#include<cstring>
#define maxa 10000
using namespace std;
int a[maxa],b[maxa],c[maxa],d[maxa];
int main()
{
int n,i,t = 0,x,j;
scanf("%d",&n);
memset(a,0,sizeof(a));
for(i=1;i<=n;++i)
{
scanf("%d",&x);
a[x+1+t] =1;
c[i] = x+1+t;
t++;
}
for(i=1;i<=n;++i)
{
for(j=c[i];j>=1;--j)
if(a[j]==0&&b[j]==0)
{
b[j] =1;
d[i]++;
break;
}
else if(a[j]==0&&b[j])
{
d[i]++;
}
}
for(i=1;i<=n;++i)
printf("%d ",d[i]);
return 0;
}

#include <iostream>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <climits>  
#include <algorithm>
#include <set>
#include <vector>

using namespace std;


int main()
{
  int n;
  cin>>n;

  int a[1600];
  memset(a,0,sizeof(a));
  for(int i=1;i<=n;i++){cin>>a[i];}

  vector<int> ss;
  vector<int>::iterator i;
  vector<int>::iterator j;  

  for(int i=1;i<=n;i++)
    {
      ss.insert(ss.end(),a[i]-a[i-1],1);        //  1表示男生  0表示女生
      ss.insert(ss.end(),1,0);
    }

  for(i=ss.begin(); i<=ss.end()-1; i++)
    {
      int c1=0;int c0=1;                    // c1记录前面的男生数目  c0记录女生数目   

      if( (*i==0)&&(*(i-1)==1) ){cout<<1<<' ';}
      
      if( (*i==0)&&(*(i-1)==0) )
      {
        j=i;j=j-2;       
        while( (c0!=c1)||(*j!=1) )
        {
          if(*j==1){c1++;j--;}
          else if(*j==0){c0++;j--;}
        }
        cout<<c1+1<<' ';
      }      
    }

  return 0;
}

一道不错的模拟题，我们发现，如果一个女孩到上一个之间有1个男孩的话，她与之配对；若没有，就找到第一个可以配对的男孩配对。has[i]记录从i好女孩到当前一个有多少男孩，left[i]记录女孩之间有多少没有配对的，如果第一种情况就把前面所有left【i]不为0的has【i】++，否则找第一个left【i】不为0的之后从那个开始更新has，left【找到的】--。细节可以看代码
#include<cstdio>
#include<cstring>
using namespace std;
int boy[100001],ans[100001],left[100001],has[100001];
int main()
{
int n;
scanf("%d",&n);
memset(has,0,sizeof(has));
boy[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&boy[i]);
if(boy[i]>boy[i-1])
{
ans[i]=1;
left[i]=boy[i]-boy[i-1]-1;
for(int j=i;j>=1;j--)
{
if(left[j]>0)
{
has[j]++;
}
}
}
else
{
for(int j=i-1;j>=1;j--)
{
if(left[j]>0)
{
ans[i]=has[j]+1;
left[j]--;
for(int k=j;k>=1;k--)
{
if(left[k]>0)
{
has[k]++;
}
}
break;
}
}
}
}
for(int i=1;i<=n-1;i++)
{
printf("%d ",ans[i]);
}
printf("%d\n",ans[n]);
return 0;
}

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<stack>
#define N 300005
using namespace std;
stack<int> a,b;
int c[N],n,k=1;
void work(int i){
    if(k>n)
        return ;
    if(i==c[k]){
        if(k!=1)
            cout<<" ";
        k++;
        cout<<b.top()-a.top()+1;
        a.pop();
        work(i);
    }
}
void slove(){
    for(int i=1;k<=n;i++){
        a.push(i);
        b.push(i);
        work(i);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    slove();
    return 0;
}

为什么会错误
#include<iostream>
#include<cstdio>
using namespace std;
int n,k,s;
int a[1501],b[1501]={2};
int f[1501];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
for(int j=k+1;j<=a[i];j++)b[j]=0;
k=a[i];
}
/*for(int i=1;i<=n;i++)cout<<a[i]<<" ";
//for(int i=1;i<=n;i++)cout<<f[i]<<" ";
cout<<endl;*/
for(int i=1;i<=n;i++)
{
for(int j=a[i];j>=1;j++)
{
s++;
if(b[j]==0)
{
f[i]=s;
b[j]=1;
break;
}
}
s=0;
}
for(int i=1;i<=n;i++)cout<<f[i]<<" ";
return 0;
}

为什么超时啦

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define pi acos(-1.0)
#define mod 1000000007
#define INF 1e20
#define Lowbit(x) (x & (-x))
#include<memory.h>
using namespace std;
stack<int>a;
int main(void)
{
int i,j,n,m,k,b[1505],c[1505],g,flag=0;
scanf("%d",&n);
int t=0;
m=0;
for(i=1; i<=n; i++)
{
scanf("%d",&k);
for(j=1; j<=k-t; j++)
{
b[m++]=1;
}
b[m++]=0;
t=k;
}
int cnt=0,coun=0;
for(i=0; i<m; i++)
{

if(b[i]==1)
{
c[cnt++]=coun++;
a.push(i);
}
else
{
c[cnt++]=coun;
g=a.top();
a.pop();
if(flag==0)
{
printf("%d",c[i]-c[g]);
flag=1;
}
else printf(" %d",c[i]-c[g]);
}
}
printf("\n");
return 0;
}