[USACO13MAR]Poker Hands S 二分答案
时间: 2023-05-25 14:04:16 浏览: 65
题目描述
http://www.usaco.org/current/data/sol_poker.html
提示
本题可以使用二分答案,设当前二分的答案为 $x$,那么只需按照从大到小的顺序考虑每张牌该如何分配即可。
具体而言,对于每张牌,我们尝试将它放进当前最小的手牌中,如果能放进去就放,否则就另起一手,把这张牌加到新的一手牌中。如果最后整张牌能够放完,那么就说明 $x$ 是可行的,否则 $x$ 不可行。
使用二分答案时,注意 $R$ 值需要先单调不降地排序。
代码
相关问题
[USACO13MAR]Poker Hands S 二分答案代码
该代码使用二分答案来搜索最大的牌面,即从A开始尝试,每次将答案范围缩小一半。如果存在一种牌面大于等于当前答案,则更新答案的下限,否则更新上限。这个过程最终会收敛到唯一的解。时间复杂度O(N log M),其中N是手中牌的数量,M是最大牌面。注:该代码仅用于参考,因为它不直接统计出答案。
```
#include <bits/stdc++.h>
using namespace std;
int val(char c) {
if (isdigit(c)) return c - '0';
else if (c == 'T') return 10;
else if (c == 'J') return 11;
else if (c == 'Q') return 12;
else if (c == 'K') return 13;
else return 14; // Ace
}
int main() {
vector<int> hand;
for (int i = 0; i < 5; i++) {
string card; cin >> card;
hand.push_back(val(card[0]));
}
sort(hand.begin(), hand.end());
int ans = 1;
for (int p = 2; p < 15; p++) {
int lo = ans, hi = 5;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (hand[mid-1] < p) lo = mid;
else hi = mid-1;
}
ans = max(ans, 5 - lo + 1);
}
cout << ans << endl;
return 0;
}
```
1682: [Usaco2005 Mar]Out of Hay 干草危机
这是一道经典的贪心算法题目,题目描述如下:
有 n 头牛,第 i 头牛需要 a[i] 单位的干草,现在有 m 捆干草,第 j 捆干草可以提供 b[j] 单位的干草。每头牛只能吃一捆干草,每捆干草也只能给一头牛吃。问最少需要多少捆干草才能满足所有牛的需求。
解题思路:
考虑将牛的需求和干草的提供都按照从大到小的顺序排序。然后从需求最大的牛开始,依次寻找能够满足其需求的干草,如果找到了就将该干草从列表中删除,直到所有的牛的需求都得到满足。
具体实现可以使用两个指针分别指向需求和干草的排序后的位置,然后使用 while 循环不断地寻找能够满足当前需求的干草,直到所有的需求都得到满足。
代码如下: