PTA乙级题 1065. 单身狗(25)

【题目链接】

这题比较容易运行超时，下面是大佬未超时算法。

#include<iostream> 
#include<cstdio> 
#include<set> 
#include<cstring> 
using namespace std;  
int book[100000];  
{  
  int n,m;  
  set<int> num,v;  
  int a,b;  
  memset(book,-1,sizeof(book));
  scanf("%d",&n);  
  for(int i = 1;i <= n;i++)
  {  
    scanf("%d%d",&a,&b);  
    book[a] = b;  
    book[b] = a;  
  }  
  scanf("%d",&m);  
  for(int i = 0;i<m;i++)
  {  
    scanf("%d",&a);  
    v.insert(a);  
  }  
  int cnt = 0;  
  for(set<int>::iterator ite = v.begin();ite != v.end();ite++)
  {  
    if(v.find(book[*ite])==v.end())  
    num.insert(*ite);
  }  
  printf("%d\n",num.size());  
  for(set<int>::iterator ite = num.begin();ite != num.end();ite++)
  book[cnt++] = *ite;    
  if(num.size()!=0)
  {  
    printf("%05d",book[0]);  
    for(int i = 1;i<cnt;i++)
    printf(" %05d",book[i]);    
  }  
}

我的代码有两个点运行超时，也放出来吧。

#include<stdio.h>
#include<string.h>
int main()
{
    int i,j,m,n;
    scanf("%d",&n);
    int a[n][2],b[n][2];
    memset(b,0,sizeof(b));
    for (i=0;i<n;i++)
    scanf("%d %d",&a[i][0],&a[i][1]);
    scanf("%d",&m);
    int c[m];
    for (i=0;i<m;i++)
    {
        scanf("%d",&c[i]);
        for (j=0;j<n;j++)
        {
            if (a[j][0]==c[i])
            {
                b[j][0]=1;
                break;
            }
            if (a[j][1]==c[i])
            {
                b[j][1]=1;
                break;
            }
        }
    }
    for (i=0;i<n;i++)
    {
        if (b[i][0]!=1||b[i][1]!=1)
        {
            a[i][0]=-1;
            a[i][1]=-1;
        }
    }
    for (i=0;i<m;i++)
    {
        for (j=0;j<n;j++)
        {
            if (c[i]==a[j][0])
            {
                //将该项与末项换位置 
                c[i]+=c[m-1];
                c[m-1]=c[i]-c[m-1];
                c[i]=c[i]-c[m-1];
                i--;//重复判断 
                m--;//剔除-1元素 
            }
            if (c[i]==a[j][1])
            {
                c[i]+=c[m-1];
                c[m-1]=c[i]-c[m-1];
                c[i]=c[i]-c[m-1];
                i--;
                m--;
            }
        }
    }
    printf("%d\n",m);
    for (i=0;i<m-1;i++)
    {
        for (j=0;j<m-1-i;j++)
        {
            if (c[j]>c[j+1])
            {
                c[j]+=c[j+1];
                c[j+1]=c[j]-c[j+1];
                c[j]-=c[j+1]; 
            }
        }
    }
    for (i=0;i<m;i++)
    {
        if (i!=0)
        printf(" ");
        printf("%05d",c[i]);
    }
}