APCS程式檢測 -實作題1060304 第4題 基地台

APCS程式檢測 -實作題1060304 第4題 基地台

最小直徑是1
最大直徑是 floor((最大座標點 – 最小座標點) / 基地台個數) + 1;
列舉出來檢查是否能包含全部的點

檢查是否可以完全覆蓋的程式碼

bool IsCovered(int nDiameter, int* pArray, int N, int K)
{
	int nCoverage = 0;
	int nCoverageNum = 0;

	for (int i = 0; i < N; i++)
	{
		if (pArray[i] <= nCoverage)
			continue;

		nCoverage = pArray[i] + nDiameter;
		nCoverageNum++;

		if (nCoverageNum > K)
			return false;

		if ((nCoverageNum <= K) && (pArray[N - 1] <= nCoverage))
			return true;
	}

	return false;
}

完整程式碼

#include <iostream>
#include <cmath>
#include <sstream>
#include <string>
using namespace std;

void BubbleSort(int* pArray, int nNum);
bool IsCovered(int nDiameter, int* pArray, int N, int K);

int main()
{
	int N;
	int K;

	//輸入 N K
	string strInput;
	getline(cin, strInput);
	stringstream delim(strInput);
	string pch;

	getline(delim, pch, ' ');
	N = stoi(pch);

	getline(delim, pch, ' ');
	K = stoi(pch);

	//宣告服務點陣列
	int* pPosition = new int[N];
	for (int i = 0; i < N; i++)
		pPosition[i] = 0;

	//輸入服務點陣列
	string strInput2;
	getline(cin, strInput2);
	stringstream delim2(strInput2);
	string pch2;

	for (int i = 0; i < N; i++)
	{
		getline(delim2, pch2, ' ');
		pPosition[i] = stoi(pch2);
	}

	int nLowerBound;	//最小直徑
	int nUpperBound;	//最大直徑
	
	BubbleSort(pPosition, N);	//排序

	nLowerBound = 1;
	nUpperBound = ((pPosition[N - 1] - pPosition[0]) / K) + 1;

	int nAnswer = 0;
	for (int i = nLowerBound; i < nUpperBound; i++)
	{
		if (IsCovered(i, pPosition, N, K))	//檢查是否能涵蓋所有服務點
		{
			nAnswer = i;
			break;
		}
	}

	cout << nAnswer << endl;
	
	delete[] pPosition;

	system("pause");
	return 0;
}

bool IsCovered(int nDiameter, int* pArray, int N, int K)
{
	int nCoverage = 0;
	int nCoverageNum = 0;

	for (int i = 0; i < N; i++)
	{
		if (pArray[i] <= nCoverage)
			continue;

		nCoverage = pArray[i] + nDiameter;
		nCoverageNum++;

		if (nCoverageNum > K)
			return false;

		if ((nCoverageNum <= K) && (pArray[N - 1] <= nCoverage))
			return true;
	}

	return false;
}

void BubbleSort(int* pArray, int nNum)
{
	int nTemp;
	for (int i = 0; i < (nNum - 1); i++)
	{
		for (int j = 0; j < (nNum - 1 - i); j++)
		{
			if (pArray[j] > pArray[j + 1])
			{
				nTemp = pArray[j];
				pArray[j] = pArray[j + 1];
				pArray[j + 1] = nTemp;
			}
		}
	}
}

用前面的列舉方式可能會很花時間
所以可以使用二分搜尋法
降低一些時間

完整程式碼(使用二分搜尋法)

#include <iostream>
#include <cmath>
#include <sstream>
#include <string>
using namespace std;

void BubbleSort(int* pArray, int nNum);
bool IsCovered(int nDiameter, int* pArray, int N, int K);

int main()
{
	int N;
	int K;

	//輸入 N K
	string strInput;
	getline(cin, strInput);
	stringstream delim(strInput);
	string pch;

	getline(delim, pch, ' ');
	N = stoi(pch);

	getline(delim, pch, ' ');
	K = stoi(pch);

	//宣告服務點陣列
	int* pPosition = new int[N];
	for (int i = 0; i < N; i++)
		pPosition[i] = 0;

	//輸入服務點陣列
	string strInput2;
	getline(cin, strInput2);
	stringstream delim2(strInput2);
	string pch2;

	for (int i = 0; i < N; i++)
	{
		getline(delim2, pch2, ' ');
		pPosition[i] = stoi(pch2);
	}

	int nLowerBound;	//最小直徑
	int nUpperBound;	//最大直徑

	BubbleSort(pPosition, N);	//排序

	//使用二分搜尋法
	nLowerBound = 1;
	nUpperBound = (int)floor((pPosition[N - 1] - pPosition[0]) / K) + 1;

	int nMed = 0;
	while (nLowerBound <= nUpperBound)
	{
		nMed = (int)floor((nLowerBound + nUpperBound) / 2);
		if (IsCovered(nMed, pPosition, N, K))		//檢查是否能涵蓋所有服務點
			nUpperBound = nMed;
		else
			nLowerBound = nMed + 1;

		if (nLowerBound == nUpperBound)
			break;
	}

	cout << nMed << endl;

	delete[] pPosition;

	system("pause");
	return 0;
}

bool IsCovered(int nDiameter, int* pArray, int N, int K)
{
	int nCoverage = 0;
	int nCoverageNum = 0;

	for (int i = 0; i < N; i++)
	{
		if (pArray[i] <= nCoverage)
			continue;

		nCoverage = pArray[i] + nDiameter;
		nCoverageNum++;

		if (nCoverageNum > K)
			return false;

		if ((nCoverageNum <= K) && (pArray[N - 1] <= nCoverage))
			return true;
	}

	return false;
}

void BubbleSort(int* pArray, int nNum)
{
	int nTemp;
	for (int i = 0; i < (nNum - 1); i++)
	{
		for (int j = 0; j < (nNum - 1 - i); j++)
		{
			if (pArray[j] > pArray[j + 1])
			{
				nTemp = pArray[j];
				pArray[j] = pArray[j + 1];
				pArray[j + 1] = nTemp;
			}
		}
	}
}