1682: [Usaco2005 Mar]Out of Hay 干草危机

这是一道经典的贪心算法题目，题目描述如下：

有 n 头牛，第 i 头牛需要 a[i] 单位的干草，现在有 m 捆干草，第 j 捆干草可以提供 b[j] 单位的干草。每头牛只能吃一捆干草，每捆干草也只能给一头牛吃。问最少需要多少捆干草才能满足所有牛的需求。

解题思路：

考虑将牛的需求和干草的提供都按照从大到小的顺序排序。然后从需求最大的牛开始，依次寻找能够满足其需求的干草，如果找到了就将该干草从列表中删除，直到所有的牛的需求都得到满足。

具体实现可以使用两个指针分别指向需求和干草的排序后的位置，然后使用 while 循环不断地寻找能够满足当前需求的干草，直到所有的需求都得到满足。

代码如下：

相关问题

[USACO13MAR]Poker Hands S 二分答案

题意

有一组牌，每张牌由一个字符串表示，字符串中的第一个字母表示牌的点数（A、K、Q、J、T、9、8、7、6、5、4、3、2），第二个字母表示牌的花色（S、H、D、C 表示黑桃、红桃、方块、梅花）。例如："TH" 表示 10 黑桃。你的任务是输出一组最大的牌。我们可以将所有牌分成三类：

- 对子 (Pair) - 两张牌有相同的点数；
- 两对 (Two Pairs) - 两组对子，每组对子有相同的点数，且第一组的点数大于第二组；
- 三个 (Three of a Kind) - 三张牌有相同的点数；
- 顺子 (Straight) - 所有五张牌点数连续，`"A"` 可以在顺子的开始或结尾；
- 同花 (Flush) - 所有五张牌花色相同；
- 三条 (Three of a kind) - 三张牌有相同的点数；
- 四条 (Four of a Kind) - 四张牌有相同的点数；
- 同花顺 (Straight flush) - 同时是顺子和同花；
- 皇家同花顺 (Royal flush) - 同时是顺子、同花，且最大点数为 `"A"`。

如果两组牌的点数一样，那么我们会比较他们的大小。点数从大到小排列为：`A`、`K`、`Q`、`J`、`T`、`9`、`8`、`7`、`6`、`5`、`4`、`3`、`2`。

输入格式

输入文件名为 `"poker.in"`。第一行一个整数，表示五张牌。接下来五行，每行表示一张牌。

输出格式

输出文件名为 `"poker.out"`。输出一行五个字符串表示最大的牌。每个字符串的前两位表示点数，后两位表示花色。

思路

由于每张牌有两个属性，即点数和花色，因此可以把两个属性分开排序。分别按照点数和花色排序后，再根据牌型的判断条件，判断最大的牌型即可输出。

判断牌型的顺序为前后顺序，如果有更上层的牌型，就不用再考虑下层的牌型了。

所以考虑一个独立的函数，输入一个排完序的五张牌，返回最大的牌型，若最大牌型不止一件，则返回最大牌型的最大点数。

判断牌型的顺序是：

- 判断皇家同花顺：
- 当前牌是否为“`TS`”、“`JS`”、“`QS`”、“`KS`”、“`AS`”；
- 判断是否为同花顺。
- 判断同花顺：先转换为顺子判断，再判断是否为同花。
- 判断四条：有四张点数相同的牌。
- 判断三条和两对：先判断有没有 3 张点数相同的牌，再判断有无两对。
- 判断两对：
- 找到点数相同的第一对牌；
- 找到点数相同的第二对牌，它的点数不能与第一对牌的点数相同；
- 判断第三张牌，它的点数与其中的一个点数相同，与另一个点数不同。
- 判断三条、两对和对子：依次判断有多少张点数相同的牌。

具体实现见代码。

代码

[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;
}