BOJ 8980-速達

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

質問する

下図に示すように、直線道路には、左から右に順に1番の村があります.町の貨物を運ぶトラックがあり、トラックの本部は1番町の左側にあります.このトラックは本部を出発し、1番町から最後の町まで右に行き、町の貨物を運んだ.

村ごとに配送する荷物を箱に入れて送ります.本部は箱を送る村番号、箱を受け取る村番号、箱を送る箱の数を知っています.箱は同じ大きさです.トラックには最大で入れられる箱の数、つまりトラックの容量があります.このトラックを利用して、以下のすべての条件を満たす場合、できるだけ多くの箱を配送します.

条件1:トラックに箱を積むと、この箱は受け入れられた村でしか降りられません.

条件2:トラックは通る村に戻らない.

条件3:箱の中に一部しか配送できない可能性があります.

村の数、トラックの容量、箱の情報(送信された村番号、受信された村番号、箱の数)を指定すると、1台のトラックが運ぶ最大の箱の数が得られるプログラムを作成します.しかし、受け取った村番号はいつも送信した村番号より大きい.
例えば、トラック容量が40であると仮定すると、送信される箱は以下の表のようになる.
送信された接魔村の箱数1210132011430024203420
これらの箱について、出荷方法を考えてみましょう.
(1)1番村に到着後
箱をトラックに積み込み、以下のようにします.△1番村から4番村に届いた箱は30箱のうち10個入っています.
送信された受信魔の村箱数121013201430
(2)2番村に到着後
トラックに積まれた箱のうち、村番号2人の箱10個が出荷された.△このときトラックに残っている箱は30個ありました.
次に以下のように箱を積む.△このときトラックの箱は40個あった.
送迎馬村の箱数2310
(3)3番村に到着後
トラックに積まれた箱の中から、届いた村番号3人分の箱30個が取り外され配送されます.△このときトラックに残っている箱は10個ありました.
次に以下のように箱を積む.△このときトラックの箱は30個ありました.
送り出した接馬村の箱数3420
(4)4番村に到着後
届いた村番号4名様の箱の下30個を配送いたします
前述したように、配送された全箱70個.これは配送できる最大の箱数です.

入力

入力された最初の行は、村数Nとトラック容量Cとの間のスペースです.Nは2以上2000以下の整数、Cは1以上10000以下の整数である.次の行で、送信されるボックス情報の個数M.Mは1以上10000以下の整数である.次のM行では、送信ボックスの村番号、受信ボックスの村番号、送信ボックスの数(1以上10000個の整数)を示す正の整数がスペースを隔てています.箱を受け取る村番号は出した村番号より大きい.

しゅつりょく

1行1台のトラックが配送できる最大箱数を出力します.

に近づく

これは面白いグリディ問題です.
これらの問題の中で、どのようにソートするかが最も重要です.
本問題では,到着都市を基準とした順位付けが核心である.
Nの最値が2000なのでO(N)²)時間の複雑さで十分です.
従って、始点から終点までの梱包数を確認するとともに、巡回も可能である.

に答える

まず,到着都市を基準に昇順ソートを行うためにpqに入れる.
各ノードには、始点から終点-1までの値のbox数があり、最大値をcntに格納します.
そしてまた巡回するときは、プラスできる最低価格をnumに保存します.
numをansに追加し、さらに巡回するときにnumをboxに追加すればいいです.

#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 };
#define piii pair<pair<int, int>, int>


int N, C, M, a, b, c, box[2001], ans = 0;

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

	MS(box, 0);
	CIN3(N, C, M);
	priority_queue<piii, vector<piii>, greater<piii>> pq;
	while (M--)
	{
		CIN3(a, b, c);
		pq.push({ {b, a}, c });
	}
	while (!pq.empty())
	{
		int start = pq.top().first.second;
		int end = pq.top().first.first - 1;
		int num = pq.top().second;
		pq.pop();
		int cnt = 0;
		FUP(i, start, end)
		{
			cnt = max(cnt, box[i]);
		}
		FUP(i, start, end)
		{
			num = min(num, C - cnt);
		}
		ans += num;
		FUP(i, start, end)
		{
			box[i] += num;
		}
	}
	COUT(ans);

	return 0;
}