4 贪心

sy149: 最优装箱 简单

https://sunnywhy.com/sfbj/4/4/149

有n个箱子需要装上一艘轮船，已知第i个箱子的重量为$w_i$，轮船的载重为W。问在不超过轮船载重的前提下，最多能把多少个箱子装上轮船。

输入描述

第一行两个正整数n、W（$1\le n\le {10}^5$、$1\le W\le {10}^7$），分别表示箱子个数和轮船载重。

第二行个正整数$w_i$（$1\le w_i\le {10}^7$），表示n个箱子的重量。

输出描述

输出两个整数，分别表示能装上轮船的箱子个数和总重量，用空格隔开。

样例1

输入

5 11
7 2 9 1 11

输出

3 10

解释

能将重量分别为7、2、1的箱子装上轮船（此时箱子个数最多），总重量为10。

n, w_raw = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cnt = 0
w = w_raw
for i in range(n):
    if a[i] > w:
        break
    cnt += 1
    w -= a[i]
print(cnt, w_raw - w)

sy150: 整数配对 简单

https://sunnywhy.com/sfbj/4/4/150

有两个正整数集合S、T，其中S中有n个正整数，T中有m个正整数。定义一次配对操作为：从两个集合中各取出一个数a和b，满足$a\in S$、$b\in T$、$a\le b$，配对的数不能再放回集合。问最多可以进行多少次这样的配对操作。

输入描述

第一行两个正整数n、m（$1\le n\le n{10}^4$、 $1\le m\le {10}^4$），分别表示和中正整数的个数。

第二行n个正整数$a_i$（$1\le a_i\le {10}^5$），表示中的个正整数。

第三行m个正整数$b_i$（$1\le b_i\le {10}^5$），表示中的个正整数。

输出描述

输出一个整数，表示最多的配对操作次数。

样例1

输入

3 3
2 5 3
3 3 4

输出

2

解释

2与其中一个3配对，3与另一个3配对，5无法和4配对。因此最多配对两次。

n, m = map(int, input().split())
*a, = map(int, input().split())
*b, = map(int, input().split())
a.sort()
b.sort()
first = 0
second = 0
cnt = 0

while first < n and second < m:
    if a[first] <= b[second]:
        cnt += 1
        first += 1
        second += 1
    else:
        second += 1

print(cnt)

https://sunnywhy.com/sfbj/4/4/151

https://sunnywhy.com/sfbj/4/4/152

https://sunnywhy.com/sfbj/4/4/153

https://sunnywhy.com/sfbj/4/4/154