白駿-2529号不等号


質問する
不等式が与えられると、その不等式関係を満たす最大、最小の整数が求められる.
の意見を打診
一番左から、最大値は:
最小値はできるだけ少ないと思います.
できるだけ大きい数量ですか?
でもできるだけ大きい数?繰り返すことができない最大の数...彼を見つけなければならない
どうして私がどんな手段を使ったか知ってるの?
使用可能な数値を配列に格納し、最大値を回転して決定し、使用後に表示しますか?
でも毎回修正するたびに配列をめぐって何を決めるよりも、
前に決めた数、つまり前の数だけを見て、記号を満たす値を加算します.
いいと思う
これはもっとグリディに似ていると思います.
最大値取得に基づく実施方法および例
前からできるだけ多く参加します.
不等号の最大値(9876543210)を作ってみましょう.
矛盾を起こせば.
現在表示されている場所で、すぐに前の値を入力します.
(前の値-元の値)、前の数-1でいいです
ex)
不等号>><の場合
9>><<
最初に入れられる最大数は9!
9>8><<
">"なので次の大数8を加えます.
9>8>7<<
そして大数7を入れます.
9>8>7<6< (x)
本来なら次の大数6の番だが、「<」なので、6を加えると矛盾が生じる.
9>8>6<7< (o)
今見ている位置は7の前の7-1を置いて6に変えます!
9>8>6<7<5 (x)
もう5、前の7より大きいため
9>8>5<6<7 (o)
今の位置に7を置いて7を置いて-1を置いて-6も-1を置いて!
左の値が大きいほど良いので、一番少ない前の数だけ-1という感じです.
++の実装は以下のコードで確認してください!
++他の人が解いたことも確認しました.
作成可能なすべてのシーケンスを作成して、矛盾があるかどうかを決定し、最大値を求める方法.
彼はできるだけ大きな数値などの方法を使って、いくつの不等号があるかを見た.
コード#コード#
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
	int k;
	char temp;
	int maxResult[15];
	int minResult[15];

	cin >> k;

	maxResult[0] = 9;
	minResult[0] = 0;
	//맨 처음에 가능한 제일 큰 수, 제일 작은 수를 넣어줌

	//for문 돌면서 앞에서 부터 값을 넣어간다
	for (int i = 1; i <= k; i++) {
		cin >> temp;
		if (temp == '<') {
			//최대값 구하는 도중에 모순생김
			int beforeResult = maxResult[i - 1];
			maxResult[i] = beforeResult; //현재 보는 자리에 바로 앞 수 넣어				 
			//바로 앞의 값 - 원래 넣으려는 값 (beforeResult - (9 - i)) 만큼 앞 수들을 보면서
			for (int j = 1; j <= beforeResult - (9 - i); j++) {
				maxResult[i - j]--; //-1 씩 해줘
			}

			//모순 없이 가능한 제일 작은 수 넣어줌
			minResult[i] = i;
		}
		else { //'>'일 때
			//모순 없이 가능한 제일 큰 수 넣어줌
			maxResult[i] = 9 - i;

			//최소값 구하는 도중에 모순생김
			int beforeResult = minResult[i - 1];
			minResult[i] = beforeResult;
			//바로 원래 넣으려는 값 - 앞의 값 (i - beforeResult) 만큼 앞 수들을 보면서
			for (int j = 1; j <= i - beforeResult; j++) {
				minResult[i - j]++; //+1 씩 해줘
			}
		}
	}

	for (int i = 0; i < k + 1; i++) {
		cout << maxResult[i];
	}

	printf("\n");

	for (int i = 0; i < k + 1; i++) {
		cout << minResult[i];
	}

	return 0;
}