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

 题目描述

有两个正整数集合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<=bfound = true;//找到了count ++;//配对数加一break;//找到了就跳出内层循环，i++，j++，继续下一轮往后查找}}if(!found){//如果都没找到直接跳出break;}}printf("%d",count);
return 0;
}