APCS程式檢測 -實作題1050305 第3題 線段覆蓋長度

APCS程式檢測 -實作題1050305 第3題 線段覆蓋長度

一般陣列都是從 0 算起，但這題從 1 算起，所以陣列總數 +1，第 0 格就盡量不去使用它。

宣告一個 bool 陣列，先以題目說明來做解釋。

再將所有的 true 總和起來，就可以得到答案

完整程式碼

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

void SetLine(bool* line, int nStart, int nEnd);	//設定線段

int main()
{
	//處理輸入- n個線段
	string strInput;
	getline(cin, strInput);
	int N = stoi(strInput);

	//測試資料 M 的最大值
	const int M = 10000000+1;

	//建立陣列
	bool* line = new bool[M];
	for (int i = 0; i < M; i++)
		line[i] = false;

	//將輸入的資料設定進線段
	int nStart = 0;
	int nEnd = 0;
	for (int i = 0; i < N; i++)
	{
		getline(cin, strInput);
		stringstream delim(strInput);
		string pch;

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

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

		//設定線段
		SetLine(line, nStart, nEnd);
	}

	//加總
	int nLineNum = 0;
	for (int i = 1; i < M; i++)
	{
		if (line[i] == true)
			nLineNum++;
	}

	//輸出
	cout << nLineNum << endl;

	//delete
	delete[] line;

	system("pause");
	return 0;
}
//設定線段
void SetLine(bool* line, int nStart, int nEnd)
{
	for (int i = nStart + 1; i <= nEnd; i++)
		line[i] = true;
}

直接使用
bool line[M];
會當機喔！這問題比較複雜，可參考這裡
http://legnaleurc.blogspot.com/2007/06/cstack-overflow.html