【晴问算法】入门篇—贪心算法—整数配对

 题目描述

有两个正整数集合S、T，其中S中有n个正整数，T中有m个正整数。定义一次配对操作为：从两个集合中各取出一个数a和b，满足a∈S、b∈T、a≤b，配对的数不能再放回集合。问最多可以进行多少次这样的配对操作。

 输入描述

输出描述

输出一个整数，表示最多的配对操作次数。

样例1

输入

3 3

2 5 3

3 3 4

输出

2 

解释

2与其中一个3配对，3与另一个3配对，5无法和4配对。因此最多配对两次。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100;//代码习惯书写，定义一个常量，便于修改长度
int s[MAXN]; 
int t[MAXN];

int main(){
	int n, m;
	cin >> n >> m;
	for(int i=0;i<n;i++){
		cin >> s[i];
	}
	for(int i=0;i<m;i++){
		cin >> t[i];
	}
	sort(s,s+n);//将数组s和t分别从小到大排序
	sort(t,t+m);
	int count = 0;
	for(int i=0;i<n;i++){//外循环从s开始遍历
		bool found = false; //在内循环每次都初始默认没找到
		for(int j=0;j<m;j++){
			if(s[i] <= t[j]){//满足题意a<=b
				found = true;//找到了
				count ++;//配对数加一
				break;//找到了就跳出内层循环，i++，j++，继续下一轮往后查找
			}
		}
		if(!found){//如果都没找到直接跳出
			break;
		}
	}
	printf("%d",count);
return 0;
}