#2170スクライブc++

3528 ワード
baekjoon algorithm sweeping テキストリンク
最も有名な計算ジオメトリアルゴリズム設計モードであり、通常、走査アルゴリズムは直線走査と呼ばれ、平面平行移動のアルゴリズムを利用して水平線または垂直線で所与の平面を「掃く」ことで問題を解決する.
問題の例では、長さ(1,3)、(2,5)、(3,5)、(6,7)の4つのセグメントがあります.以下に示すように、それを図に描きます.

ここで、複数回線引きをした場合、一度だけ計算される線引きの全長は(1、5)、(6、7)長さと5となる.
なお、スクライブでは2点の位置(x,y)を取得し、xの値に基づいて昇順に並べて問題を解決します.
struct Line {
	int start;
	int end;
};

Line line[MAX];
まず、各セグメントに2つの点を入力する必要があるため、1つのセグメントの始点(start)、終点(end)構造を作成します.

bool compare(Line A, Line B){
	if (A.start < B.start) return true;
	return false;
}

void solution() {
	sort(line + 1, line + N + 1, compare);
	int answer = 0;
	int left = -INF;
	int right = -INF;

	for (int i = 1; i <= N; i++) {
		if (line[i].start <= right)
			right = max(right, line[i].end);
		else {
			answer += right - left;
			left = line[i].start;
			right = line[i].end;
		}
	}
    answer += right - left;
}
lineに値を入力すると、line[i].startを基準に昇順に並べます.
現在のline[i].始点が右より小さいか等しいかは、現在の左、右の指定部分と重なることを意味します.
つまり、図から赤い線を引くと、左=1、右=3になります.
新しいオレンジ色の線が入ってくるとオレンジ色の線がstart=2、オレンジ色の線.end=5.
ここで、オレンジ色線のstartはrightより小さいが、オレンジ色線のend 5はright in 3より大きい.したがって、権利は5に更新される.
範囲外の新しい線分が入っている場合は、前の左、右を基準に線分の長さを答えに保存し、左、右を再更新します.

sortとcompare関数を見てみましょう.
  • sort(start,end):[start,end]範囲内のパラメータを昇順(デフォルト、default)でソートします.
  • sort(start,end,compare)を使用して、ユーザー定義関数(compare)に基づいてソートします.
  • sort(start end,greater<資料型>()を使用して[start,end)範囲の因子を降順に並べます.
    • 私たちはline[i]です.startを基準に並べ替えるので、2回使用する場合はとても便利に並べ替えることができます.

    しかし、いつもタイムアウトが発生して、他の人はコードを見て、結果はstructと宣言しないで、vectorフォーマットを使って、だから私もついて行きました.
    pair<「タイプ」と「タイプ」>は、それぞれ2つの指定したタイプの値を格納します.
    保存された値はです.first .2回目は別々に近づくことができます.
    2つの関連する値を一緒に保存でき、管理が容易です.
    特に,関連する2つの値のうち,それぞれの条件に従って並べ替えた結果を得ようとする場合に用いるとよい.このような場合にぴったりのタイプなので、多くの人が利用しています.
    #include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N;
vector<pair<int, int>> v;

void input() {
	cin >> N;
	int s, e;
	for (int i = 0; i < N; i++) {
		cin >> s >> e;
		v.push_back({ s,e });
	}
}

void solution() {
	sort(v.begin(), v.end());

	int left = v[0].first;
	int right = v[0].second;
	long long answer = 0;

	for (int i = 1; i < N; i++) {
		if (v[i].first <= right) {
			right = max(right, v[i].second);
		}
		else {
			answer += right - left;
			left = v[i].first;
			right = v[i].second;
		}
	}
	answer += right - left;
	cout << answer << endl;
}
int main() { 
	input();
	solution();

	return 0;
}

    コード全体が前述のstructと変わらず、時間超過が続きます.なぜか、まだ見つかっていません.
    git(3) - github
    [python][伯俊#1546]平均