質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

681閲覧

Atcoder Beginner Contest 212-Dをpriority_queueのpairで解いたがコンパイルエラーになる

alice4649

総合スコア17

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2021/07/31 13:50

先ほどABC212-D(https://atcoder.jp/contests/abc212/tasks/abc212_d)を解いたのですがCEになってしまいました。(多分原因はpriority_queueをpairでして、どこかでミスしていると思いますが。)どこが原因かご教授願います。

C++

1#include <bits/stdc++.h> 2using namespace std; 3#define ll long long 4#define ld long double 5#define rep(i,a,n) for (ll i = a;i<(n);++i) 6#define all(v) v.begin(),v.end() 7#define pu(n) push_back(n) 8/*--------------------------------------------*/ 9int main(){ 10 ll q;cin>>q; 11 ll b; 12 vector<ll>rnt; rnt.pu(0); 13 ll ka=0; 14 priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<ll>>x; 15 rep(i,0,q){ 16 ll a;cin>>a; 17 if(a==1){ 18 cin>>b;x.push(make_pair(b,ka)); 19 } 20 if(a==2){ 21 cin>>b;rnt.pu(rnt[ka]+b);ka++; 22 } 23 if(a==3){ 24 auto e=x.top(); 25 ll bi=e.first;ll r=e.second;x.pop(); 26 ll cnt=rnt[rnt.size()-1]-rnt[r]; 27 28 cout<<bi+cnt<<endl; 29 } 30 } 31 return 0; 32}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

c++

1priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<ll>>x;

greater<ll>greater<pair<ll,ll>>に変更すると、エラーは消えます。
が、どうやらこれではWAのようです。

例えばP={1,2,1,3,3}の場合、P_2での加算がpriority_queue内で反映されずに出力されてしまうからだと考えられます。
少しわかりにくい書き方になってしまいましたが、

6 1 3 2 3 1 5 3 2 2 3

この入力を使って人の手でプログラムの流れを追うとどこがおかしいか分かりやすいと思います。

P_i=2の時に、以降のP_j=1で追加する値についてrnt[ka]だけ引いてから出力の際に足しなおすという処理が必要になるはずです。

投稿2021/07/31 14:49

rasennn

総合スコア8

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

alice4649

2021/08/03 10:36

難しいですね汗 ありがとうございます
guest

0

[回答ではありません]

priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<ll>>x;

greater<ll> は何を比較するのが目的ですか?

投稿2021/07/31 14:12

episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

alice4649

2021/07/31 14:18

priority_queueでpair.firstを昇順に並べたいと思っています。 正直、そこはコピペしていじったのでgreater<ll>の意味はよく分かりません
episteme

2021/07/31 14:24

だったら struct greater_first { bool operator()(const pair<ll,ll>& a, const pair<ll,ll>& b) const { return a.first > b.first; } }; ... priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater_first>x;
alice4649

2021/07/31 14:30

ありがとうございます。struct はこういうときに使うのですね。
episteme

2021/07/31 14:42

class でも構わんですが...
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問