洛谷-P 1803-乱れたyyy/線分被覆

5539 ワード

経典貪欲問題(区間不交差問題)
テーマの背景はもうすぐnoipになって、yyyはとても緊張します!タイトルの説明は現在各ojにnn試合があり、各試合の開始、終了の時点は知っている.yyyは、多くの試合に参加すればするほど、noipは試験を受けることができると思っています.だから、彼はせいぜいいくつかの試合に参加できることを知りたいと思っています.yyyはこんにゃくなので、一つの試合に参加するには最後までやり遂げなければならず、2つ以上の試合に同時に参加することはできない.入力フォーマットの最初の行は整数nであり、次にn行の各行は2つの整数ai,bi(ai

サンプル出力

解題の構想これは経典の貪欲な問題(区間が交差しない問題)で、私たちはまず分析します:yyyを最も多くの試合に参加させるには、私たちは試合の終了時間ごとに小さいから大きいまでソートすることができて、ソートの過程の中で、開始時間に対しても同時に交換しなければなりません.だから、ここで、開始時間と終了時間の関連バインドに構造体を用いた.sort関数を用いてboolタイプのカスタム関数と組み合わせて開始時間と終了時間を終了時間の小さい順に並べ替え、その後、endt変数が前のフィールドの終了時間を表すことを定義し、後の開始時間と比較し、前のフィールドの終了時間が次のフィールドの開始時間より早い場合、endtを次のフィールドの終了時間に等しくするカウントします.問題は最も多くの試合に参加しなければならないとは言っていないので、私たちはすべての試験時間の長さを考えなくてもいいです.Emm言い換えれば、時間は1-3と2-3の試験でどちらでもいいです.私のACコードを添付します.

#include 
#include 
using namespace std;

struct match
{
     
	int start;
	int end;
}m[1000005];

bool cmp(match a, match b)
{
     
	return a.end < b.end;
}

int main()
{
     
	int n, i, endt = 0, sum = 0;
	cin >> n;
	for (i = 0; i < n; i++)
	{
     
		cin >> m[i].start >> m[i].end;
	}
	sort(m, m + n, cmp);
	for (i = 0; i < n; i++)
	{
     
		if (endt <= m[i].start)
		{
     
			endt = m[i].end;
			sum++;
		}
	}
	cout << sum;
	return 0;
}

Webpack変換less、CSS Modulesを開いた後に背景のピクチャーは失効します

jQueryチェーン操作