d478: 共同的數 - 簡易版

2019-08-29

內容

因為學長覺得 d136 太可怕，所以出一題簡單版的 XD

小潘跟小花都有很多個正整數，自己的數不會有重覆出現的，而且都是遞增排列。

現在她們想要知道，兩個人的數有幾個重覆的呢？

輸入

第一行有兩個數字 n,m。 (1<=n<=100,1<=m<=10000)

接著共有 n 筆測資，每筆測資共有兩行，分別代表兩個人擁有的數，每行共有 m 個數。

所有數字都不大於 2³-1。

2 6
1 5 6 8 9 13
3 4 5 7 8 11
4 6 7 14 16 23
6 9 12 13 16 23

輸出

每筆測資請輸出一個數字，

代表兩個人的數有幾個重覆的。

2
3

解題思路

兩陣列皆為遞增排列，所以不用排序直接從頭開始比較比較兩陣列

若相同，數量 + 1，兩陣列索引都加一
若不同，值較小的陣列索引加一

當某一陣列數字用完了就跳出，得到的數量就是答案。

本題輸入測資頗大，做輸入優化可以省不少時間。

完整程式碼

AC (21ms, 1.1MB)

#include <stdio.h>
#define BUFSIZE 1048576
#define MAX 10010

unsigned int lhs[MAX], rhs[MAX];

inline char readChar()
{
    static char buffer[BUFSIZE], * now = buffer + BUFSIZE, * end = buffer + BUFSIZE;
    if (now == end)
    {
        if (end < buffer + BUFSIZE)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZE, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readUInt(unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

int main()
{
    int n, m, l, r, count;
    scanf(" %d %d", &n, &m);
    while (n--)
    {
        count = l = r = 0;
        for (int i = 0; i < m; i++)
            readUInt(&lhs[i]);
        for (int i = 0; i < m; i++)
            readUInt(&rhs[i]);
        for (;;)
        {
            if (lhs[l] < rhs[r])
            {
                if (++l == m) break;
            }
            else if (rhs[r] < lhs[l])
            {
                if (++r == m) break;
            }
            else
            {
                count++;
                if (++l == m) break;
                if (++r == m) break;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}