BOJ 253-スクールバス

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

質問する

住宅難を解決するために、直線道路に沿っていくつかの団地が建てられた.また、この団地の住民のために、道路の1つの場所に学校が新設された.マンション団地は遠いので、スクールバスとスクールバスしか乗れないに違いない.
各マンション団地と学校の位置は道路上の座標で与えられ、各マンション団地にはここに住む学生の数がある.スクールバスは朝学校を出発し、各団地の学生を乗せて帰校する.このスクールバスは定員を超えて学生を乗せることができず、すべての学生が学校に行くまでこの過程を繰り返します.

以上のルールに従って、すべての学生を学校に行かせる例です.マンション団地A、B、Cはそれぞれ座標0、2、5カ所、団地に住む学生はそれぞれ1、2、1名である.2つのポイント間の距離は、2つのポイント座標の差として定義されます.せいぜい4人乗りのスクールバスで座標4の学校を出発して、すべての学生を学校に行かせる時、バスはまずBに行って2人乗り、Aに行って1人乗ってから学校に戻って、距離2+2+4=8を移動します.更に学校から団地Cに移動して、一人を乗せて帰ってきて、移動距離は1+1=2で、総移動距離は8+2=10です.
学校の位置、マンションごとの位置、学生数、スクールバスの定員が与えられる場合は、すべての学生が学校に通うために必要なスクールバスの総移動距離の最大値を計算するプログラムを作成してください.

入力

1行目には3つの正の整数N,K,Sがスペースを隔てて順次与えられる.1番目の整数Nはマンション団地の数であり、2<=N<=30000である.2番目の整数Kは1<=K<=2000で、スクールバスの定員です.3番目の整数Sは学校の位置を表す.2行目からN+1行目の間には、各マンション団地の位置と、その団地の学生数を表す整数がある.学校と団地の座標は0以上100000以下で、これらの座標はすべて異なっています.各マンションの生徒数は1以上2000以下である.

しゅつりょく

1行目に与えられた入力では、走行バスの最小移動距離が出力される.最小移動距離は10000000を超えない.

に近づく

学校を基準にして、最も遠いマンション団地が先に聞こえるのは明らかだ.
どのように表現されているかの問題のようで、左と右を分けました.
そして、一瞬ごとに、彼は一番遠いアパートに学生を迎えに行きます.

に答える

まずfastの座標を基準にsortを行った.
そして、一番近い左座標インデックスを真ん中に置いて見つけました.
その後idxを宣言し、0からmidまでチェックし、ansに左遠座標の値を追加します.
同様に,N−1からmid+1を確認しながらansに右遠座標の値を増やした.

#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, K, S, ans = 0;
pair<int, int> apart[30000];

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

	CIN3(N, K, S);
	FUP(i, 0, N - 1) CIN2(apart[i].first, apart[i].second);
	sort(apart, apart + N);
	int mid = N - 1;
	FUP(i, 0, N - 1)
	{
		if (S < apart[i].first)
		{
			mid = i - 1;
			break;
		}
	}
	if (mid != -1) // 왼쪽
	{
		int idx = 0;
		while (idx <= mid)
		{
			int first = apart[idx].first;
			int remain = K;
			while (idx <= mid)
			{
				if (apart[idx].second > remain)
				{
					apart[idx].second -= remain;
					break;
				}
				remain -= apart[idx++].second;
			}
			ans += (2 * (S - first));
		}
	}
	if (mid != N - 1) // 오른쪽
	{
		int idx = N - 1;
		while (idx > mid)
		{
			int first = apart[idx].first;
			int remain = K;
			while (idx > mid)
			{
				if (apart[idx].second > remain)
				{
					apart[idx].second -= remain;
					break;
				}
				remain -= apart[idx--].second;
			}
			ans += (2 * (first - S));
		}
	}
	COUT(ans);

	return 0;
}