BOJ 1461-図書館

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

質問する

勢俊は図書館で働いています.図書館の開放時間が終わったので、勢俊は人々がむやみに置いた本を持って帰る必要がある.勢俊は今0にいて、人々がむやみに置いた本も0にあります.各本に元の位置がある場合は、すべての本を元の場所に戻すために必要な最小ステップ数を計算するプログラムを作成します.勢俊は一歩一歩座標を歩いて、本の元の位置は整数座標です.本を全部元の場所に戻したら、もうゼロに戻る必要はありません.そして勢俊は一度に最大M冊の本を手に入れることができる.

入力

一行目は本の個数N、セジュンが一度に取れる本の個数Mです.2行目は本を出す位置を与える.Nは10000以下の自然数、Mは10000以下である.本の位置は0ではありません.その割引は10000以下です.

しゅつりょく

1行目に正解を出力します.

に近づく

この問題で考えなければならないことは大体3つある.
最初のステップでは、右(+)と左(-)を分割します.
第二に、最後に最も割引された数字にアクセスします.
第三に、最大数のM冊の本を持って遠くへ行きます.
それを考えれば、簡単に解けます.

に答える

LとRベクトルが生成され、シンボルごとに異なる管理が行われる
各セクションの値は、大きな数からソートされ、遠くの位置を移動してから、インデックスをM個移動します.
最後にアクセスした回数は,LとRの最初のインデックスのうち終端値がより大きい箇所を除いた.

#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;
}