参照標準コンテナ二分探索P0125

参照で直して lower_bound で探す

品物 n 個の名前・価格・在庫を構造体（struct）の std::vector に入れ、コマンド m 個で直したあと、問い合わせ q 個に答えよ。
品物を名前で探す関数は vector の中の要素を参照（Item&）で返し、直す関数はその参照を受け取って要素をその場で変える。
コマンドをすべて処理したあと、ラムダの比較関数を渡した 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 言語の解答

この問題は、vector の中の要素を参照（Item&）で返して受け取るやり方と、ラムダを受け取る C++ 標準ライブラリの std::sort・std::lower_bound を練習する問題なので、C++ だけを受け付けます（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 は空の品物のままです。
要素を変える range-for は auto& です。
③ std::sort は安定ソートではないので、同じ価格どうしの順は決まっていません。
比較ラムダに名前まで書く必要があります（std::stable_sort を使っても入力の順になるだけで、名前順にはなりません）。
④ lower_bound は x 以上の最初の要素、upper_bound は x より大きい最初の要素なので、upper_bound を使うと価格がちょうど x の品物を飛ばします。
比較ラムダの引数の順も違い、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';    }}