滴滴2017筆記試験

あるレストランにはnつのテーブルがあり、各テーブルにはパラメータがあります.aが収容できる最大人数です.mロットのお客様がいて、各ロットのお客様には2つのパラメータがあります:b人数、c予想消費金額.相席が許可されていない場合は、アルゴリズムを実装して一部のお客様を選択し、総予想消費金額が最大になるようにしてください.
説明を入力:

    m+2 。
       n(1 <= n <= 50000),m(1 <= m <= 50000)
    n   a,             ,     ,    32 int   。
   m ，      b,c。     i             ,     ,    32 int   。

出力の説明:

      ,            

入力例1:

3 5
2 4 2
1 3
3 5
3 7
5 9
1 10

出力例1:
20
タイトルは最大金額から選ぶべきですが、人数を満たせばいいです.c++のstlにはlowerがあります.bound関数は、クエリが所定の値以上の反復器である(ちなみにupper_bound関数は、等しいよりも大きい選択ではなく、大きい選択である)
これも別のブログの書き方を参考にしています.1テーブルあたりの人数と金額が一体なので、自然と構造体を書こうと思います.
まず金額降順に並べ、金額が同じ場合は人数昇順に並べます(人数が少なく、金額が大きい場合がほしいからです)
だってlower_boundはmapにのみ有効でvectorは使えないので、ここでは強引にmapを構築しました.このmapのキーは2行目の数字で、値は固定値に与えられ、意味がありません.
#include #include #include #include using namespace std; struct my_node {int b; int c;my_node(int x_b, int x_c) :b(x_b), c(x_c){}; }; bool cmp(my_node node1, my_node node2) {if (node1.c!=node2.c){return node1.c > node2.c;}else{return node1.b < node2.b;} } int main() {int n, m;multimaptable_renshu;while (cin>>n>>m){for (int i = 0; i < n;i++){int temp; cin >> temp;table_renshu.insert(make_pair(temp, 1));}vectorm_data;for (int i = 0; i < m;i++){int b; int c;cin >> b >> c;my_node temp(b,c);m_data.push_back(temp);}sort(m_data.begin(),m_data.end(), cmp);//int ans=0;long long ans = 0;for (int i = 0; i < m;i++){multimap::iterator it = table_renshu.lower_bound(m_data[i].b);if (it != table_renshu.end()){ans += m_data[i].c;table_renshu.erase(it);}}cout << ans << endl;}return 0; }