問題出典 : Nowcoder
スタックとソート (nowcoder.com)
問題の解析
- 各要素の挿入に対して二つの動作が可能である
- スタックに挿入
- 直接出力（挿入後に即座に削除）
- この二つの動作をどう選択するか？
- 問題の要件：出力されるシーケンスは降順に並べる（ソート不可能な場合は辞書式で大きいものに近づける）
- 最大値が最初にスタックから取り出されるのが最適
- 最大値であり、かつ最も早く取り出せる（スタックトップと未挿入要素の比較）
コード実装
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
stack<int> s;
int n, a[maxn];
int maxh[maxn]; // maxh[i] は a[i, n] の最大値を示す。未挿入要素の最大値を表す
int main()
{
cin >> n;
// 要素の挿入を記録
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
// maxh配列の計算
maxh[n] = a[n];
for(int i = n - 1; i >= 1; i--) // maxh[i] は [i, n] の範囲内の最大値
maxh[i] = max(a[i], maxh[i + 1]);
// スタックのシミュレーション、要件に従って挿入・削除 ---> 目標シーケンスを得る
for(int i = 1; i <= n; ++i)
{
if(a[i] == maxh[i]){ // 未挿入中の最大値を削除
cout << a[i] << " "; // 直接削除
}
else s.push(a[i]);
// cout << s.size() << " "<< s.top() << " "<< s.size() && s.top();
// cout << '\n';
while(s.size() && s.top() > maxh[i + 1]) // スタックトップが未挿入要素の最大値以下になるように保つ
{
cout << s.top() << " ";
s.pop();
}
}
cout << '\n';
return 0;
}
ポップ・ポップ（泡） (nowcoder.com)
問題の解析
- 問題の目的：隣接する同じ泡を結合する
- 小さな泡二つ = 大きな泡一つ
- 大きな泡二つ = 空
- 実装方法：
- スタックデータ構造を使用する。
- なぜか？ 隣接する泡を処理したいからで、スタックはトップ要素のみを管理するのでこの要件に合う。
- 実装戦略：
- 現在の泡とスタックトップの泡を比較する（スタックが空でないとき）、空の場合は現在の泡をスタックに挿入。
コード実装
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<char> a; // 泡処理用スタック
stack<char> b; // 元の泡の順序を保持するための補助スタック
string s;
while (cin >> s) {
for (int i = 0; i < (int)s.length(); ++i) {
if (!a.empty()) {
if (a.top() == 'o' && a.top() == s[i]) { // 小泡でスタックトップと一致
a.pop(); // 大泡へ合成
if (!a.empty() && a.top() == 'O') // 大泡と一致するものが残っているか確認
a.pop();
else
a.push('O');
} else if (a.top() == 'O' && a.top() == s[i])
a.pop();
else
a.push(s[i]);
} else
a.push(s[i]);
}
while (!a.empty()) { // スタック a を補助スタック b に移す --> 元の順序を復元
b.push(a.top());
a.pop();
}
while (!b.empty()) { // 処理後の泡を出力
cout << b.top();
b.pop();
}
cout << '\n';
}
return 0;
}
[HNOI2003]オペレーティングシステム (nowcoder.com)
問題の解析
- 各プロセスには優先度が割り当てられる → 単一要素による優先度ではない
- どのデータ構造を使って待機プロセスのキューを管理すべきか？
- ある構造体を思い出す：優先度付きキュー（特徴：通常、キューの先頭要素にアクセスする → 優先度が最も高い要素）
- 構造体 node（プロセス番号、到着時間、実行時間、優先度）を定義し、優先度付きキューのコンテナとして使用できる。構造体をコンテナとして使う場合、デフォルトでは < 演算子で比較されるため、< 演算子のオーバーロードが必要
- これでキューができたら？
- 定義されたルールに従ってプロセスを操作できる（プロセススケジューリング）
- 目標は、完了可能なプロセスを実行し、完了できないものはキューに入れ、一つずつ取り出すこと
コード実装
#include<iostream>
#include<queue>
using namespace std;
struct node{
int a, b, c, d;
bool operator <(const node & x) const{ // 優先度付きキューの < 演算子のオーバーロード
if(d == x.d)return b > x.b; // 優先度が同じ場合、到着時間が早い方が優先
else return d < x.d; // d が大きいほど優先度が高い
}
};
node x; // 新たに到着したプロセス、execque は待機キュー
priority_queue<node>execque; // 待機キュー、デフォルトは大頂点ヒープ、トップ要素が最も優先度が高く最初に出る
int t; // 現在時刻、初期値は 0
int main(){
while(cin >> x.a >> x.b >> x.c >> x.d){ // 現在のプロセスが到着
// 実行可能なものはすぐに実行
while(!execque.empty() && t + execque.top().c <= x.b){ // キューが空でなく、先頭要素が実行可能であれば
node curnode = execque.top();
t += curnode.c;
cout << curnode.a << " " << t << '\n';
execque.pop();
}
// 実行不可なものは待機キューに追加
if(!execque.empty()){ // キューが空でなく、待機キューの先頭要素の優先度が現在到着した x より低い場合
node curnode = execque.top();
curnode.c = curnode.c - (x.b - t); // 先頭要素の実行時間を更新し、再度キューに挿入
execque.pop();
execque.push(curnode);
}
execque.push(x); // 待機キューの処理後、現在のプロセスを待機キューに追加
t = x.b; // 現在時刻の更新
}
// 待機キューの要素を処理
while(!execque.empty()){
node curnode = execque.top();
t += curnode.c;
cout << curnode.a << " " << t << '\n';
execque.pop();
}
return 0;
}