BOJ 1276-架橋

タイムアウトメモリ制限正解の送信正解正解正解正解正解率2秒128 MB 27611810443.697%

質問する

2010年に芦原区に多層橋梁を架けることが決定し、実際の設計が完成した.しかし、これは当たり前かもしれませんが、橋脚がなく、橋が空に浮かぶことはあり得ないので、橋脚を適当に設置します.
橋脚の取り付け規則は以下の通りである.橋の両端は別の橋や地面に取り付け、できるだけ橋脚の長さを最小限に抑える必要があります.しかし、橋はすべて平らで、橋は立てなければなりません.橋脚は他の橋脚と交差してはならない.

例は上図のとおりです.左図は設計された橋、右図は橋脚を置く橋を示しています.そして橋脚の全長が14であることがわかります.
問題は、橋があるときに総橋脚の長さとを求めることです.

入力

第1行は、ブリッジの個数を表す整数N(1≦N≦100)を与える.2行目からN+1行目までは、各行に橋の位置を表す3つの整数Y,X 1,X 2があり、これは(X 1,Y)~(X 2,Y)まで橋があることを意味する.すべての座標は10000を超えない自然数です.次に、床のY座標を0とする.(X2 > X1+1)

しゅつりょく

1行目は橋脚の長さの合計を出力します.

に近づく

xの範囲は0から10000なので、下から橋を架けながら最大高さを保存すれば良いと思います.
実際には、橋が重なることもなく、橋の数が最大100個ということなので、十分に体現しても良いでしょう.
金の問題は簡単すぎるのではないでしょうか.このような考えが生まれたのは、論理的な間違いがないので、そのまま体現されているからだ.

に答える

pair,pair,int,int>はこの資料型が大嫌いですが、構造体を作りたくないので、このようにしました.
y軸(高さ)を基準としてアレイをソートし、x 1座標とx 2座標の交差角の高さをansに遍歴的に加算した.
そしてx 1~x 2における高さ(height配列)を初期化した.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, ans = 0, height[10000];
pair<int, pair<int, int>> arr[100];


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

	MS(height, 0);
	CIN(N);
	FUP(i, 0, N - 1)
	{
		CIN3(arr[i].first, arr[i].second.first, arr[i].second.second);
	}
	sort(arr, arr + N);
	FUP(i, 0, N - 1)
	{
		int y = arr[i].first;
		int left = arr[i].second.first;
		int right = arr[i].second.second;
		ans += (y - height[left]);
		ans += (y - height[right - 1]);
		FUP(h, left, right - 1) height[h] = y;
	}
	COUT(ans);

	return 0;
}