糖果分配
糖果分配
https://www.nowcoder.com/practice/c0e676f4cf9846c785ade34d9472951b?tpId=98&tqId=32866&tPage=3&rp=3&ru=/ta/2019test&qru=/ta/2019test/question-ranking
题目难度：二星
考察点：贪心
方法：贪心
1.分析：
对于这个题来说，我们要做的是尽可能满足越多数量的孩子，那么我们采取一个贪心的策略，即尽可能的先满足胃口较小的孩子。那么现在的问题就是如何分配糖果才能使得在贪心条件下满足条件的孩子数量最多呢？其实我们只要将读入进来的孩子胃口数组g和糖果尺寸数组s进行从小到大的排序，然后将尺寸越小的糖果分配给胃口较小的孩子就ok了。怎么操作呢？其实在排序结束之后，定义两个指针i=j=0，然后就进行遍历，如果当前的糖果尺寸可以i满足孩子的胃口，就更新答案和下标指针，即if(g[i] <= s[j]) i++, j++,ans++;否则的话，就只更新糖果尺寸的下标，即j++。当不满足(i<g.size() && j<s.size())条件时，跳出循环，最后输出答案ans就可以了。
算法实现：(1). 需要处理一下输入(使用stringstream)，得到数组g和s。
(2). 将上述两个数组进行从小到大排序。
(3). 定义两个指针i=j=0,分别进行遍历数组g和s，然后根据上述的条件进行判断和更新答案。
(4). 输出答案ans。
2.复杂度分析：
时间复杂度：O(nlog(n))空间复杂度：O(n)
3.代码：
#include <bits/stdc++.h>
using namespace std;
vector<int> g, s;
int main(){
string str; getline(cin, str);
stringstream ss(str);
int x; while(ss>>x) g.push_back(x);
getline(cin, str);
stringstream ss2(str);
while(ss2>>x) s.push_back(x);
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, j = 0, ans = 0;
while(i<g.size() && j<s.size()) {
if(g[i] <= s[j]) i++, ans++;
j++;
}
cout<<ans<<endl;
return 0;
}
投递腾讯云智研发等公司9个岗位 >
查看11道真题和解析