NOJ 2024インスタックシーケンスおよびアウトスタックシーケンス(stack)
インスタックシーケンスとアウトスタックシーケンス
時間制限(通常/Java):1000 MS/3000 MS 実行メモリ制限:65536 KByte合計コミット:205 試験合格:50
説明
出入りスタックシーケンス{A}に、{A}の各要素値が等しくないことを保証し、辞書シーケンスが最大の出スタックシーケンスを出力する.
入スタックシーケンス{A}=1,2,9,4,6,5の場合、辞書シーケンスの最大の出スタックシーケンスは9,6,5,4,2,1である.
入力
1行目の整数n(1<=n<=100).次にスタックシーケンス{A},n個の正の整数ai(0しゅつりょく
1行、辞書シーケンスの最大のスタックシーケンス. 各数字はスペースで区切られています.
サンプル入力
6 2 1 9 4 6 5
サンプル出力
9 6 5 4 1 2
ヒント
null
テーマソース
NUPT
タイトルリンク:http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2024
テーマの分析:後ろから前へ増分の序列を探して、それぞれの増分の序列の最大値とその下の標準を保存して、要求によってスタックに入ってスタックを出ます
コード:
時間制限(通常/Java):1000 MS/3000 MS 実行メモリ制限:65536 KByte合計コミット:205 試験合格:50
説明
出入りスタックシーケンス{A}に、{A}の各要素値が等しくないことを保証し、辞書シーケンスが最大の出スタックシーケンスを出力する.
入スタックシーケンス{A}=1,2,9,4,6,5の場合、辞書シーケンスの最大の出スタックシーケンスは9,6,5,4,2,1である.
入力
1行目の整数n(1<=n<=100).次にスタックシーケンス{A},n個の正の整数ai(0
1行、辞書シーケンスの最大のスタックシーケンス. 各数字はスペースで区切られています.
サンプル入力
6 2 1 9 4 6 5
サンプル出力
9 6 5 4 1 2
ヒント
null
テーマソース
NUPT
タイトルリンク:http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2024
テーマの分析:後ろから前へ増分の序列を探して、それぞれの増分の序列の最大値とその下の標準を保存して、要求によってスタックに入ってスタックを出ます
コード:
#include <cstdio>
#include <stack>
using namespace std;
int const MAX = 1e3 + 2;
int cur[MAX], pos[MAX], num[MAX];
stack <int> s;
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &num[i]);
// ,
for(int i = n; i > 0; i--)
{
if(cur[i] > num[i - 1])
{
cur[i - 1] = cur[i];
pos[i - 1] = pos[i];
}
else
{
cur[i - 1] = num[i - 1];
pos[i - 1] = i - 1;
}
}
for(int j = 0, i = 0; i < n; i++)
{
// ，
if(s.empty() || s.top() < cur[j])
{
for(int k = pos[j]; j <= k; j++)
s.push(num[j]);
}
// ，
//
if(i != n - 1)
{
printf("%d ", s.top());
s.pop();
}
else
printf("%d
", s.top());
}
}