描述
已知一些people和一些糖果,第i个people的需求因子为gi,第j个糖果的大小为sj,当某个糖果的大小sj大于等于某个people的需求因子gi时,代表该糖果可以满足该people,求使用这些糖果最多能满足多少个people。
注意,1个people最多只能用1个糖果满足
输入
共3行
第1行,使用空格隔开的两个整数n、m,其中n表示people的数量,m表示糖果的数量;1≤n、m≤5000
第2行,n个使用空格隔开的整数,表示每个people的需求因子1≤gi≤109
第3行,m个使用空格隔开的整数,表示每个糖果的大小1≤sj≤109
输出
一行,一个整数,表示给定的糖果最多可以满足多少个people
样例输入
2 3
1 2
1 2 3
样例输出
2
将读入的两个数组排序,而后双指针遍历即可。
#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
int main()
{
int m, n;
cin >> m >> n;
vector<int> people;
vector<int> candle;
for (int i = 0; i < m; i++)
{
int num;
cin >> num;
people.push_back(num);
}
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
candle.push_back(num);
}
sort(people.begin(), people.end());
sort(candle.begin(), candle.end());
int i = 0, j = 0;
while (i < m && j < n)
{
if (people[i] <= candle[j])//如果糖果大于人,则人可吃
{
i++;
j++;
}
else //否则,不能满足人,则该糖果也无用了。
{
j++;
}
}
cout << i << endl;
return 0;
}