{ }codelper
引用标准容器二分查找P0125

用引用修改，用 lower_bound 查找

把 n 件商品的名字、价格和库存存进结构体（struct）的 std::vector，用 m 条命令修改后，回答 q 个查询。
按名字查找商品的函数以引用（Item&）返回 vector 中的元素，修改函数接收该引用并就地修改元素。
处理完所有命令后，用传入 lambda 比较函数的 std::sort 按价格从低到高排列，价格相同时按名字的字典序排列。
查询用 std::lower_bound 回答。
第一行是 n，接下来 n 行为 "名字 价格 库存"。
下一行是 m，接下来 m 行每行一条命令，为 "sell 名字 k"、"restock 名字 k"、"price 名字 p" 之一。
sell 在库存不少于 k 时减去 k，不足时什么也不改。
restock 把库存加上 k。
price 把价格改为 p。
下一行是 q，接下来 q 行每行一个整数 x。
对每个查询，输出排好的列表中价格低于 x 的商品数 c，以及价格不低于 x 的第一件商品，格式为 "c 名字 价格 库存"。
若没有这样的商品，输出 "c none"。

输入
1 ≤ n ≤ 1000，0 ≤ m ≤ 1000，1 ≤ q ≤ 1000。
名字为 1 到 8 个小写英文字母且互不相同，命令中只出现已有的名字。
1 ≤ 价格, p ≤ 1,000,000,000。
初始库存为 0 到 1000，1 ≤ k ≤ 1,000,000。
1 ≤ x ≤ 1,000,000,001（均为整数）
输出
每个查询一行
样例 1 · stdin
4
pear 7 1
fig 7 2
apple 9 3
kiwi 2 4
3
sell fig 2
sell kiwi 5
price apple 7
4
7
3
1
8
stdout
1 apple 7 3
1 apple 7 3
0 kiwi 2 4
4 none
样例 2 · stdin
2
tea 10 5
jam 20 5
2
restock tea 3
price tea 30
3
20
21
31
stdout
0 jam 20 5
1 tea 30 8
2 none
main.py
输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写？查看各语言题解 · 1 种语言题解

本题只接受 C++，因为它练习的是以引用（Item&）返回和接收 vector 中元素的方式，以及 C++ 标准库中接收 lambda 的 std::sort、std::lower_bound（Java、Python、JS 总是按引用处理对象，无需选择；C# 虽有 ref 返回，但类的对象总是引用，平时很少用到；C 没有引用，要用指针）。
在 Craykon 中则把字典放进列表，用 排序(比较函数) 排序，再自己写二分查找。
四个陷阱：① 即使 findItem 返回 Item&，用 auto item = findItem(...) 接收时，auto 会去掉引用而产生副本。
卖出的数量和改过的价格都不会留在 vector 里。
要用 auto& 或 Item& 接收。
② for (auto item : shelf) std::cin >> item.name ... 同样读进了副本，vector 里仍是空商品。
修改元素的范围 for 要用 auto&。
③ std::sort 不是稳定排序，相同价格之间的顺序不确定。
比较 lambda 里必须写上名字（用 std::stable_sort 也只会保持输入顺序，而不是名字顺序）。
④ lower_bound 找第一个不小于 x 的元素，upper_bound 找第一个大于 x 的元素，所以用 upper_bound 会跳过价格恰好为 x 的商品。
比较 lambda 的参数顺序也不同：lower_bound 接收 (元素, 值)，upper_bound 接收 (值, 元素)。
用找到的迭代器减去 shelf.begin()，就得到它前面的商品数 c。
排序要在处理完所有命令之后进行，因为价格一变，位置也会变。

C++main.cpp · 66 行
#include <algorithm>#include <iostream>#include <string>#include <vector> struct Item {    std::string name;    int price;    int stock;}; // 이름으로 찾아 vector 안의 원소 그 자체(참조)를 돌려준다. 이름은 반드시 있다Item& findItem(std::vector<Item>& shelf, const std::string& name) {    auto it = std::find_if(shelf.begin(), shelf.end(), [&](const Item& x) { return x.name == name; });    return *it;} // 바꾸는 함수는 Item&를 받는다: 복사본이 아니라 shelf 안의 원소를 바꾼다void update(Item& item, const std::string& op, int k) {    if (op == "sell") {        if (item.stock >= k) item.stock -= k;    } else if (op == "restock") {        item.stock += k;    } else {        item.price = k;    }} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);     int n;    std::cin >> n;    std::vector<Item> shelf(n);    for (auto& item : shelf) std::cin >> item.name >> item.price >> item.stock;  // auto&: 원소에 바로 읽어 넣는다     int m;    std::cin >> m;    for (int i = 0; i < m; i++) {        std::string op, name;        int k;        std::cin >> op >> name >> k;        Item& item = findItem(shelf, name);  // auto&도 된다. auto만 쓰면 참조를 돌려받아도 복사한다        update(item, op, k);    }     // 가격 순, 같으면 이름 순. std::sort는 같은 것끼리의 차례를 지키지 않으니 이름까지 적는다    std::sort(shelf.begin(), shelf.end(), [](const Item& a, const Item& b) {        if (a.price != b.price) return a.price < b.price;        return a.name < b.name;    });     int q;    std::cin >> q;    for (int i = 0; i < q; i++) {        int x;        std::cin >> x;        // 가격이 x 이상인 첫 물건: lower_bound의 비교 함수는 (원소, 찾는 값) 차례로 받는다        auto it = std::lower_bound(shelf.begin(), shelf.end(), x,                                   [](const Item& item, int value) { return item.price < value; });        std::cout << (it - shelf.begin());        if (it == shelf.end()) std::cout << " none\n";        else std::cout << ' ' << it->name << ' ' << it->price << ' ' << it->stock << '\n';    }}