usaco-1.1.2 贪婪的礼物送礼者

GitHub跳转原题关系图返回列表

用 map 把名字映射为下标，按送礼顺序模拟：人均 m/cnt、余数自留，最后按读入顺序输出每人净额。

OJ: roj

题目 ID: 2001

难度:入门

标签:入门模拟字符串哈希表python

创建: 2026-10-01 02:15

更新: 2026-10-06 08:59

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

nn 个人按输入顺序编号 1∼n1\sim n（n≤20n\le 20），每人初始钱数为 00。随后给出若干条送礼记录直到文件末尾：先给出送钱人名字，接着一行两个整数 mm、cntcnt，表示送出 mm 元给 cntcnt 个人；若 cnt>0cnt>0，下面 cntcnt 行每行一个接收者名字。每人分到 ⌊m/cnt⌋\lfloor m/cnt\rfloor 元，余数 m mod cntm\bmod cnt 由送钱人自留；cnt=0cnt=0 时不发生任何转移。按读入顺序输出每个人最终钱数。

思路

把名字用 map<string,int> 映射成下标，维护一个钱数数组。逐条读取送礼记录：若 cnt>0cnt>0 则算出商和余数，送钱人扣掉实际分出的钱，每个接收者加上商；cnt=0cnt=0 则跳过。最后按名字输入顺序输出数组。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 02:15
# update_at: 2026-10-01 02:18

import sys


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    names = [next(data).decode() for _ in range(n)]    # 题面第 2 ~ n+1 行：n 个名字
    index = {name: i for i, name in enumerate(names)}  # 名字 → 编号，查人 O(1)

    money = [0] * n
    for giver in data:                                 # 每组记录以送钱人的名字开头，读到文件末尾
        amount, cnt = int(next(data)), int(next(data))
        share, left = divmod(amount, cnt) if cnt else (0, 0)  # cnt 为 0 时不做除法
        money[index[giver.decode()]] += left - amount  # 送出的钱扣掉，除不尽的余数自己留下
        for _ in range(cnt):
            money[index[next(data).decode()]] += share  # 每位接收者拿到平分的 share

    print('\n'.join(f"{name} {value}" for name, value in zip(names, money)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 08:59
 * update_at: 2026-10-06 08:59
 */

#include <iostream>
#include <string>
#include <map>
using namespace std;

typedef long long ll;

const int MAXN = 25; // 人数上限，n <= 20

string names[MAXN];       // 按输入顺序保存名字
map<string, int> id;      // 名字 -> 下标
ll money[MAXN];           // 每个人的最终钱数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> names[i];
        id[names[i]] = i;
    }

    string giver;
    while (cin >> giver) { // 每条记录以送钱人名字开头，读到 EOF 结束
        ll m;
        int cnt;
        cin >> m >> cnt;

        ll share = 0, left = 0;
        if (cnt != 0) {            // cnt 为 0 时不做除法
            share = m / cnt;
            left = m % cnt;
        }

        int g = id[giver];
        money[g] += left - m;      // 送钱人扣掉真正分出去的部分，余数自留
        for (int i = 0; i < cnt; i++) {
            string receiver;
            cin >> receiver;
            money[id[receiver]] += share;
        }
    }

    for (int i = 0; i < n; i++) {
        cout << names[i] << " " << money[i] << "\n";
    }
    return 0;
}