BOJ-10816デジタルカード2ソリューション(C++)

問題リンク
白駿10816号-デジタルカード2

解決策

  最初に問題が発生した場合は、入力した数値を配列として保存し、配列を折りたたまない順序に並べ替え、バイナリ検索(またはクイックまたはマージSort)を使用して各ターゲットを検索し、見つかった要素を未知のフラグ変数として非表示にして再検索します.このような方法で番組を考えることができます.
  あるいは,配列を並べ替えた後に同様の高速検索を行い,1つの値を見つければ,見つけた位置で並べ替えた配列を左右に遍歴し,長さを算出して個数のスタイルを返すアルゴリズムも可能である.

ああ。土地。いっぱい!!!

  実はこの問題はバイナリ探索、ソート、数世紀などの仕事が「全く必要ない」問題です.あなたのVerlog初期PS測位問題では、この問題のライセンスが必要な問題があります.これらの測位を見たら、すぐにこの言葉を理解することができます.
入力した整数の範囲は-1000000～1000000です.つまり、200000001の数字に関連しています.この「数字そのもの」を一つの配列と見なしてはどうでしょうか.
  もし誰かがこの問題を解決できなかったら、私は彼が上の文章を読んで膝を叩くと信じています.そうですね.この問題はPigeonhole Principleに基づいて簡単に解決できる.(アレイのサイズはintを基準とし、10億、さらにはそれ以上です.)
~>この方法で解くと,速度面では上記アルゴリズムよりはるかに速く,わずかな空間しか占めていないが,空間が限られているため問題ない.入力を簡単に受け入れ、問題を解決するだけです.
  詳細な説明は必要ありません.次はコードです.

#include <iostream>
// BOJ - 10816 Number Card 2
#define MAX_SIZE	500000
#define HASH_SIZE	10000000
using namespace std;

int target[MAX_SIZE + 1], cnt[2*HASH_SIZE + 1];

int main(void) {
	int n, m, temp;
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) { cin >> temp; cnt[temp + HASH_SIZE]++; }
	cin >> m;
	for (int i = 1; i <= m; i++) cin >> target[i];

	for (int i = 1; i <= m; i++) 
		cout << cnt[target[i] + HASH_SIZE] << '\n';

	return 0;
}