数据结构与算法实验题 9.2 材料

★实验任务

sean 要制作一种物品,他要先收集材料.制作该物品有两种方式,给出这两种方式所需要的材料,sean 还没想好要用哪种方式,他现在只好搜集足够的材料确保两种制作方式都能

满足.请问他最少需要收集多少个材料?

★数据输入

输入第一行为一个正整数 N(2 < N <= 50000)表示第一种方式所需的材料数。接下来一行输入 N 个数表示需要的材料的编号,这些数中可能有相同的数,即同一种材料可能需要多

个. 第三行为一个正整数 M(2 < M <= 50000)表示第二种方式所需的材料数。接下来一行输入 M 个数表示需要的材料的编号,这些数中可能有相同的数,即同一种材料可能需要多个. 

★数据输出

输出一行一个整数，表示最少需要收集的材料的个数。

输入示例 

3

3 1 3

3

1 1 3

输出示例

4

题目显然是求两个集合的并集（元素一样取大的那个）

#include
    
     #include
     
      using namespace std;const int MAXN=50000+10;int N,M;int a[MAXN],b[MAXN];struct data{	int num;	int cnt;}c[MAXN],d[MAXN];int main(){	scanf("%d",&N);	int i;	for(i=0;i
      
        d[j] .num)			ans+=d[j++].cnt;		else if(c[i].num < d[j] .num)			ans+=c[i++].cnt;		else if(c[i].num == d[j] .num)		{			ans= ans+(c[i].cnt >d[j].cnt ? c[i].cnt: d[j].cnt);			i++;			j++;		}	}	while(i==lenc && j