2017.8.1拼多多内推内推笔试题(3)—六一儿童节(贪心问题)

xiaoxiao2021-02-28  100

首先是题目:

六一儿童节,老师带了很多好吃的巧克力到幼儿园。每块巧克力j的重量为w[j],对于每个小朋友i,当他分到的巧克力大小达到h[i] (即w[j]>=h[i]),他才会上去表演节目。老师的目标是将巧克力分发给孩子们,使得最多的小孩上台表演。可以保证每个w[i]> 0且不能将多块巧克力分给一个孩子或将一块分给多个孩子。 输入描述: 第一行:n,表示h数组元素个数 第二行:n个h数组元素 第三行:m,表示w数组元素个数 第四行:m个w数组元素 输出描述 上台表演学生人数 输入例子 3 2 2 3 2 3 1 输出例子 1 思路:既给每个h分配一个最合适的w 因为思路比较简单下面直接给出AC代码:

#include <bits/stdc++.h> using namespace std; int n, m; priority_queue<int> pqh, pqw; int main() { cin >> n; for (int i = 0; i < n; ++i) { int h; cin >> h; pqh.push(h); } cin >> m; for (int i = 0; i < m; ++i) { int w; cin >> w; pqw.push(w); } int res = 0; while (!pqw.empty() && !pqh.empty()) { if (pqw.top() >= pqh.top()) { ++res; pqw.pop(); pqh.pop(); } else { pqh.pop(); } } cout << res; return 0; }
转载请注明原文地址: https://www.6miu.com/read-38615.html

最新回复(0)