在此处输入标题

未分类

G - queue的使用

题目大意

n张牌编号从1到n。按标号顺序从上到下叠在一起放置，你将不断执行一个操作直到牌堆里只剩下一张牌。
该操作为 1将牌堆顶部的牌移走，2将牌堆顶部的牌放到牌堆底部。
输出牌被移走的顺序和最后剩下的那张牌。

解题思路
约瑟夫问题的简单版，链表模拟即可。

参考代码

#include<cstdio>

int Next[60],Last[60];

int main(){

    int n,top,i;
    while(1){
        scanf("%d",&n);
        if(n==0)break;
        if(n==1){
            printf("Discarded cards:");
            printf("\nRemaining card: %d\n",1);
            continue;
        }

        for(i=2;i<=n;i++){
            Next[i]=i+1;
            Last[i]=i-1;
        }
        Next[n]=2;
        Last[2]=n;

        top=Next[2];
        printf("Discarded cards: 1");

        while(Next[top]!=top){
            printf(", %d",top);
            Next[Last[top]]=Next[top];
            Last[Next[top]]=Last[top];
            top=Next[Next[top]];
        }
        printf("\nRemaining card: %d\n",top);
    }
    return 0;

 }

H - stack的使用

题目大意

n列火车排队进出栈，已知n列火车排队的顺序，判断给出的出栈顺序是否合法。

解题思路

熟悉栈的应用后暴力模拟。

参考代码

#include<stdio.h>

int ans[30],a[20],b[20],stk[20],f[20];

int main(){

    int n,i,now,top,j;
    while(scanf("%d",&n)!=EOF){
        for(i=1;i<=n;i++){
            scanf("%1d",&a[i]);
            f[i]=0;
            ans[i]=-1;
        }
        for(i=1;i<=n;i++)
            scanf("%1d",&b[i]);
        top=now=0;
        for(i=j=1;i<=n;i++){
            if(f[b[i]]){
                if(stk[top]!=b[i])break;
                ans[++now]=1;
                top--;
            }
            else{
                for(;j<=n&&a[j]!=b[i];j++){
                    stk[++top]=a[j];
                    f[a[j]]=1;
                    ans[++now]=0;
                }
                ans[++now]=0;
                ans[++now]=1;
                f[a[j++]]=1;
            }
        }
        if(now==2*n){
            puts("Yes.");
            for(i=1;i<=now;i++){
                if(ans[i])puts("out");
                else puts("in");
            }
        }
        else puts("No.");
        puts("FINISH");
    }
    return 0;
}

I - queue的使用

题目大意
给出一个队列，队列里装着若干数字，每次取出队首元素，询问队列中是否有元素严格大于队首元素，如果存在将队首元素放到队列末尾，反之删除队首元素。
求位于第k个位置的元素是第几个被删除的。

解题思路

暴力模拟。

参考代码

//code 1
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;


struct node{int left,right,val,num;}p[200];


int main(){

    int T,n,k,i,tim,a,b,now;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        tim=0;
        for(i=0;i<n;i++){
            scanf("%d",&p[i].val);
            p[i].num=i;
            p[i].left=(i-1+n)%n;
            p[i].right=(i+1)%n;
        }
        now=0;
        while(true){
            a=p[now].right;
            b=now;
            while(a!=b){
                if(p[a].val>p[now].val)now=a;
                a=p[a].right;
            }
            tim++;
            if(p[now].num==k)break;

            p[p[now].left].right=p[now].right;
            p[p[now].right].left=p[now].left;
            now=p[now].right;
        }
        printf("%d\n",tim);

    }
    return 0;
}


//code 2
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int a[200],r[200];

int main(){

    int T,n,m,i,j,k;
    scanf("%d",&T);
    r[0]=1;/* 2 0   1 1 */
    while(T--){

        scanf("%d%d",&n,&m);
        m++;
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
            r[i]=i;
        }
        for(i=1;i<=n;i++){
            k=i;
            for(j=i+1;j<=n;j++){
                if(a[j]>a[k])k=j;
                else if(a[j]==a[k]&&(r[j]-r[i-1]+n)%n<(r[k]-r[i-1]+n)%n)k=j;
            }
            if(k!=i){
                swap(a[k],a[i]);
                swap(r[k],r[i]);
            }
            if(r[i]==m)break;
        }
        printf("%d\n",i);
    }
    return 0;
}