PAT (Advanced Level) 1063. Set Similarity (25)

读入之后先排序。

询问的时候可以o(m)效率得到答案。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;

struct X
{
    int m;
    int a[10000+10];
}s[60];
int n;

struct Arr
{
    int f;
    int num;
}h[200000+10];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i].m);
        for(int j=1;j<=s[i].m;j++) scanf("%d",&s[i].a[j]);
        sort(s[i].a+1,s[i].a+1+s[i].m);
        s[i].a[s[i].m+1]=0x7FFFFFFF;
    }
    int k; scanf("%d",&k);
    for(int i=1;i<=k;i++)
    {
        int A,B; scanf("%d%d",&A,&B);
        int z1=1,z2=1;
        int tot=0;
        while(1)
        {
            if(tot==s[A].m+s[B].m) break;
            if(s[A].a[z1]<s[B].a[z2])
            {
                h[++tot].f=1;
                h[tot].num=s[A].a[z1];
                z1++;
            }
            else if(s[A].a[z1]>s[B].a[z2])
            {
                h[++tot].f=2;
                h[tot].num=s[B].a[z2];
                z2++;
            }
            else
            {
                h[++tot].f=1;
                h[tot].num=s[A].a[z1];
                z1++;
            }
        }
        h[0].num=-1;
        int nc=0,nt=0;
        for(int i=1;i<=tot;i++) if(h[i].num!=h[i-1].num) nt++;
        int pos=1;
        while(1)
        {
            if(pos>tot) break;
            int yuan;
            for(int i=pos;i<=tot;i++)
            {
                if(h[i].num==h[pos].num) yuan=i;
                else break;
            }

            if(h[pos].f!=h[yuan].f) nc++;
            pos=yuan+1;
        }
        printf("%.1lf%%
",1.0*nc/nt*100);
    }
    return 0;
}