垃圾装袋(标记法)【标记思想】 |
您所在的位置:网站首页 › 一堆垃圾拼音 › 垃圾装袋(标记法)【标记思想】 |
问题 G: 垃圾装袋(点击跳转)
时间限制: 1 Sec 内存限制: 128 MB 提交: 360 解决: 84 [提交] [状态] [讨论版] [命题人:admin] 题目描述 某城市环卫部门需要对分布在城市中不同地点的 n 堆(编号为 1 到 n)垃圾进行装袋处 理。现在有 m 个(编号为 1 到 m)垃圾袋可以使用。 一个容量为 v 的垃圾袋能装入不超过容量为 v 的垃圾,一堆垃圾要求只能用一个垃圾 袋来装,一个垃圾袋也只能用来装一堆垃圾(即一个垃圾袋不能在两个地方装垃圾)。一个 垃圾袋的价格是由垃圾袋的容量来决定,容量为 v 的垃圾袋价格为 v。 请编程帮环卫部门计算要将 n 堆垃圾全部装袋,用掉的垃圾袋最少值多少钱?
输入 输入共 3 行。 第 1 行两个正整数 n 和 m,表示需要处理 n 堆垃圾,现在有 m 个垃圾袋。 第 2 行 n 个整数,依次表示每堆垃圾的容量。 第 3 行 m 个整数,依次表示每个垃圾袋的容量。
输出 输出共 1 行。 输出一个整数,如果能将所有的垃圾装入已有的袋子,则输出用掉的垃圾袋最少值多少 钱?如果无法将所有的垃圾装入 m 个袋子,则输出“-1”。 样例输入 复制样例数据 3 4 3 6 4 4 5 7 3样例输出 14
提示 有3堆垃圾,4个袋子,第1堆容量为3的垃圾用第4个容量为3的袋子装,第2堆容 量为6的垃圾用第3个容量为7的袋子装,第3堆容量为4的垃圾用第1个容量为4的袋子 装,所以用掉的垃圾袋最少值3+7+4=14。 30%的测试点输入数据保证1≤n,m≤1000 70%的测试点输入数据保证1≤n,m≤10000 100%的测试点输入数据保证1≤n,m≤50000,每个垃圾袋的容量和每处垃圾的容量 不超过10000。 代码: #include #include using namespace std; bool cmp(long long int a,long long int b) { return a |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |