170 条题解

  • 9
    @ 2017-05-07 22:25:31
    /*
    先解释一下样例
    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;
    }
    
    • @ 2017-07-26 17:25:43

      哇太感谢了, 看了半天没看懂描述

  • 6
    @ 2017-04-21 12:56:09
    #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
    @ 2020-03-06 15:02:53
    //男 男 男 男 女 男 女 男 女 女 女 女
    //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;
    }
    
    
    
  • 1
    @ 2018-07-18 10:32:46

    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;
    }

  • 0
    @ 2022-07-16 22:29:24

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

  • 0
    @ 2019-02-13 21:00:35

    纯模拟
    看到大神们的代码感觉自己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;
    }
    
    
  • 0
    @ 2018-03-13 14:52:33
    ****不用栈模拟,对于一个女孩纸,她的舞伴只能在左边,所以从当前位置往前找到一个没有访问到的一个就是她的舞伴,借助于女孩纸数组我们可以虚构出一个男孩纸数组,直接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;
    }
    
  • 0
    @ 2017-10-25 17:26:26

    模拟栈

    # 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--]);
        }
    }
    
    
  • 0
    @ 2017-09-04 19:36:15

    //#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;
    }

  • 0
    @ 2017-07-04 15:31:22

    果然还是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();
        }
    }
    
  • 0
    @ 2017-06-17 11:25:01

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

    #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;
    }
    
  • 0
    @ 2017-04-08 17:16:56
    
    #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);
        }
    }
    
  • 0
    @ 2017-02-25 18:00:34
    #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;
    }
    
  • 0
    @ 2017-01-22 20:54:11

    #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;
    }

  • 0
    @ 2016-12-15 14:38:57

    #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;
    }

  • 0
    @ 2016-11-22 02:48:05
    #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;
    }
    
  • 0
    @ 2016-11-10 07:39:15

    一道不错的模拟题,我们发现,如果一个女孩到上一个之间有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;
    }

  • 0
    @ 2016-09-22 19:17:32
    #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;
    }
    
  • 0
    @ 2016-09-08 22:10:04

    为什么会错误
    #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;
    }

  • 0
    @ 2016-05-16 19:29:54

    为什么超时啦

    #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;
    }

    • @ 2016-06-07 10:39:17

      数组太小?

信息

ID
1062
难度
4
分类
数据结构 | 点击显示
标签
递交数
3506
已通过
1396
通过率
40%
被复制
8
上传者