[白俊]18513先生(c++)

2783 ワード
テキストリンク

白駿18513泉


1.質問


質問リンク

2.方法

  • 問題アクセス
  • 社は泉域を基準として1、-1が最も近い場合、{-1,1}をデフォルト値として、家が位置すべき距離を決定します.
  • の最短距離を求める問題であるため,BFSアルゴリズムを用いる.
  • 軒を建てる場所はアクセスチェックが必要なのでsetを使いました.setまたはunordered setまたは上記の問題では、より高速なunordered setが使用されます.
  • 軒とSamterの距離を求めるために、初めてSamterの座標を入力するとQに値を入力し、BFS関数でQのサイズでもう一度whileゲートを回します.->距離が短いほど、不幸度の和が最小になるので、whileゲートが終わるたびに距離+1になります.

    • 3.コード

    #include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#include <unordered_set>	//unordered_set이 일반 set보다 속도가 빠름

using namespace std;

typedef long long ll;
int N, K;	
int dx[2] = { 1, -1 };
queue<int> Q;
unordered_set<int> s;

ll BFS()
{
	ll ans = 0, dis = 1;

	while (!Q.empty())
	{
		int size = Q.size();
		while (size--)
		{
			int housePos = Q.front();
			Q.pop();

			for (int i = 0; i < 2; i++)
			{
				int pos = housePos + dx[i];
				if (!(s.count(pos) >= 1))
				{

					K--;
					ans += dis;
					s.insert(pos);
					Q.push(pos);

					if (K == 0)
						return ans;
				}
			}
		}
		dis++;
	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		Q.push(a);
		s.insert(a);
	}
	cout << BFS() << "\n";
	return 0;
}

    4.時間の複雑さ


    BFSアルゴリズムの問題を用い,隣接行列を用いた.
    ここで,頂点ごとに接続された幹線はそれぞれ2本(1,−1)あるので,合計数はO(2 NK)であり,定数倍は無視できる.また,BFSナビゲーションでは頂点をO(NK)個,幹線もO(NK)個,O(NK+NK)=O(2 NK)=定数倍無視,時間複雑度はO(NK)とした.

    5.結果


    ラテックスのためのDevanagari音訳管
    リストの場所の変更