読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

SRM 692 div2 easy PriorityQueue

問題

問題概要

食堂にならんでいる。並んでいる順番で前から順に、その人がどんな行動をするかが与えられる。行動は2通りで、
b := 一番前に横入りする
e := 最後尾に戻る
である。先に並んでいたのに、前に横入りされると、不満がたまる。それぞれの人に対して、1度横入りされるとたまる不満が決まっている。合計どれだけ不満がたまるかを求める問題。

解法

まず、dequeを使い、bとe行動について処理して、全員の行動が終わった後にどのような順番で並んでいるかを求める。はじめに並んでいた生徒を前から順に0,1..と順番をつけると、 "ebbe"の場合、はじめは、0123だが、行動が終わった後は、2103となっている。この2103というのを前から調べていく。2は先頭にあるので不満はない。1については、はじめは1より遅くに並んでいた2が前にいるので、不満が1回たまる。0については、はじめは1,2より先に並んでいたのに、行動後は後ろに並んでいるので、不満が2回たまる。3は最初も最後も最後尾なので、不満はたまっていない。
上にあげた例の様に、現在みている数字より、おおきい数字が先にある数だけ不満がたまるので、それをすべての数字に対して行い合計をだせばよい。

ミス

priority_queue?

コード

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

class PriorityQueue{
public:
    int findAnnoyance(string S, vector <int> a){
        deque<int> dq;
        rep(i, S.size()){
            if(S[i] == 'b'){
                dq.push_front(i);
            }else{
                dq.push_back(i);
            }
        }

        int ans = 0;
        for (int i = 0; i < dq.size(); ++i){
            for (int j = 0; j < i; ++j){
                int num = dq[i];//生徒の番号
                if(num < dq[j]){//前に入られた
                    ans += a[num];
                }
            }
        }
        return ans;
    }
};