[伯俊]10159秤(c++)

1902 ワード
テキストリンク

100準10159秤


1.質問


質問リンク

2.方法

  • 問題アクセス
    -各アイテムについて、そのアイテムと比較した結果未知のアイテムの個数を出力するため、2 D配列を使用します.すなわちfloodとshallアルゴリズムを用いた問題である.
    -前の物は後ろの物より重いので、物を入力すると、
    bがaより重い場合は1とし、逆に−1とする.
    -追加のノードを生成し、三重ゲートが回転すると、通過するノードの対応する値は、探しているものの重量に等しく、0でない場合は、この値を更新します.
    -出力のためにダブルforゲートを回し、ans値にあなた以外の値を初期値として設定し、0でない場合はansを減らし、最後にansを出力します.

    • 3.コード

    #include <algorithm>
#include <iostream>

using namespace std;

int map[101][101];
//floyd-warshall 알고리즘 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, a, b, ans; 

	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = -1;
	}

	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if (map[i][k] == map[k][j] && map[i][k] != 0)
					map[i][j] = map[i][k];
 			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		ans = N - 1;
		for (int j = 1; j <= N; j++)
		{
			if (map[i][j] != 0)
				ans--;
		}
		cout << ans << "\n";
	}
	return 0;
}

    4.時間の複雑さ


    floodとshallアルゴリズムは基本的に三重ゲートであり,O(n^3)の時間的複雑さを有する.
    ここで、時間は1秒に制限され、N値は最大100であるため、100000、すなわち100万に達し、1億を超えない.
    従って、1秒以内に実現できる.

    5.結果


    17087鬼ごっこ(C++)
    TiDBがJepsenに出会った時