洛谷 U657773 - 打水题解

Tiger

发表于 2026-02-26

更新于 2026-02-26

题解

4 1.1~1.4 分钟 494

题面

小明家有 $n$ 个水井。对于第 $i$ 个水井，总共可以打出 $a_i$ 桶水，需要的总时间为 $t_i$ 。小明需要完成父母指派给他打 $x$ 桶水的任务。为防止下毒，小明父母要求小明在同一个水井中最多只能打 $m$ 桶水，超过这个限额便不能再在这个水井中打水。

为了尽快打完水玩游戏，小明希望打水的时间尽可能地短，请帮他找出一种方案，使得小明打水时间最短。

分析

这是一道典型的贪心问题。为了使小明打水的总时间尽可能短，我们要让他打每桶水消耗的时间尽可能短。我们可以将输入数据存在一个结构体数组里，将这个结构体数组的元素按照“打一桶水需要的时间”从小到大进行排序。随后，从 $x$ 开始，不断打水，直至打完。再将得到的数据按输入时的顺序整理后输出即可。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Well {
    int id;       // 原始编号
    int a;        // 总水量
    int t;        // 总时间
    int limit;    // 可打上限 min(a, m)
    int take;     // 实际取水量，初始为0
};

bool cmpByEfficiency(const Well &w1, const Well &w2) {
    // 按 t/a 升序，用交叉乘法避免浮点误差
    return (long long)w1.t * w2.a < (long long)w2.t * w1.a;
}

bool cmpById(const Well &w1, const Well &w2) {
    return w1.id < w2.id;
}

int main() {

    int n, x, m;
    cin >> n >> x >> m;
    vector<Well> wells(n);
    for (int i = 0; i < n; ++i) {
        wells[i].id = i + 1;
        cin >> wells[i].a >> wells[i].t;
        wells[i].limit = min(wells[i].a, m);
        wells[i].take = 0;
    }

    // 按效率排序
    sort(wells.begin(), wells.end(), cmpByEfficiency);

    int remaining = x;
    for (auto &w : wells) {
        if (remaining <= 0) break;
        int get = min(w.limit, remaining);
        w.take = get;
        remaining -= get;
    }

    // 按原编号排序输出
    sort(wells.begin(), wells.end(), cmpById);
    for (const auto &w : wells) {
        cout << w.id << " " << w.take << '\n';
    }

    return 0;
}