51 nod活動手配問題の2(貪欲+stl)

3407 ワード

いくつかの活動があり、i番目の開始時間と終了時間は[Si,fi]で、活動の間に重複することはできません.活動をすべて手配するには、少なくともいくつかの教室が必要ですか?
分析:一つの問題の解法に従って、各教室はできるだけ多くの活動を手配することができるかどうか、すなわち終了時間によって並べ替えて、更に衝突しない活動を貪欲に選択して、1つの教室を手配した後、残りの活動は更に1つの教室を分配して、引き続き貪欲に選択します......
反例:A:[1,2)B:[1,4)C:[5,6)D:[3,7]
終了時間順に並びましたので、お選びいたします
教室1:A C
教室2:B
教室3:D
教室が3つ必要です.
しかし、手配方法を変えれば、ADを1つの教室に配置することができ、BCは別の教室にあり、2つの教室で十分です.
だからこれまでの貪欲な策略ではこの問題を解決できなかった.
どうしよう?以前の戦略は1つの教室で手配できるすべての活動を探して、つまり教室で活動を探して、私たちは活動で教室を探すことができますか?
≪ポリシー|Policy|emdw≫:開始時間順にアクティビティを優先的にスケジュールし、競合する場合は教室を追加します.
簡単に理解すると、戦略はこのようにして、私たちは活動を開始時間の小さい順に並べ替えます.現在k個の教室が割り当てられていると仮定し(明らかにk初期は0に等しい)、現在のこの活動に対して、
(1)k個の教室のいずれかに配置できれば,その中のいずれかの教室に配置し,kは変わらない.
(2)そうでなければ,各教室の活動と衝突し,教室を1つ増やし,この活動を手配する.
この戦略は最良ですか?
kが1を増やす過程を想像してみましょう.私たちは開始時間に従ってソートしているので、現在考えているこの活動が開始されたとき、kつの教室には活動が終わっていないことを意味します(もし1つの教室の活動が終わったら、私たちはこの活動をその教室に配置して衝突せずに、kを増やす必要はありません).これは、この活動が開始された時点で、現在考えられているこの活動を含めると、(k+1)の活動が行われており、同じ時刻に(k+1)の活動が行われていることを意味し、私たちがどのように教室を手配しても、少なくとも(k+1)の教室が必要である.教室ごとに2つの活動を同時に行うことができないからです.私たちの戦略はちょうど(k+1)教室が必要なので、最適です.
この戦略は、時間軸から「マクロ」でこの問題を考慮すれば、私たちにも教えてくれます.各時点で同時に行われる活動個数を考慮すると、この時点の厚さ(活動の開始時間と終了時間を線分として想像すると、各時点に何本の線分が覆われているか、簡単に「厚さ」と理解できる)として、少なくとも最大厚さの複数の教室が必要である--その時はちょうど最大厚さの複数の活動が同時に行われていたので、私たちのこの貪欲な策略はちょうど私たちに最大の厚さの多くの教室ですべての活動を手配する案を与えた.
教室の数だけであれば、すべての開始時間と終了時間を並べ替えることができ、開始時間に遭遇すると厚さを1にし、終了時間に遭遇すると厚さを1に減らすことができ、明らかに最も初期と最後の終了時の厚さは0であり、一連の厚さの変化の過程で、ピーク値(最大値)は最も同時に行われる活動数である.私たちが少なくとも必要とする教室の数でもあります.
最後に、入出力データを提供して、あなたがプログラムを書いて、このアルゴリズムを実現して、正しいプログラムを書いてこそ、後の授業を続けることができます.
入力

        n (n <= 10000)       。
     (n + 1)   n          。
            ，          ，  1000000000

しゅつりょく

。

入力例

出力例

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct node
{
	int start;
	int end;
}a[11111];
bool cmp(node x,node y)
{
	if(x.start<y.start) return true;
	else if(x.start==y.start && x.end<y.end) return true;
	return false;
}
priority_queue<int,vector<int>,greater<int> >qq;
int main()
{
	int n,i,j,ans,t;
	cin>>n;
	for(i=0;i<n;i++) cin>>a[i].start>>a[i].end;
	sort(a,a+n,cmp);
	qq.push(a[0].end);
	ans=1;
	for(i=1;i<n;i++) {
		t=qq.top();
		if(a[i].start<t) {
			ans++;
			qq.push(a[i].end);
		}
		else {
			qq.pop();
			qq.push(a[i].end);
     	}
	}
	cout<<ans<<endl;
	return 0;
}

q神コード:
線分の交差数を計算する_--==すごいですね.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int,int> >event;
int main()
{
    int n;
    scanf("%d",&n);
    int st,ed;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&st,&ed);
        event.push_back(make_pair(st,1));
        event.push_back(make_pair(ed,-1));
    }
    sort(event.begin(),event.end());
    int cnt=0,ans=0;
    for(int i=0;i<event.size();i++)
    {
        cnt+=event[i].second;
        if(ans<cnt)ans=cnt;
    }
    printf("%d
",ans);
    return 0;
}

データの暗号化

データ構造におけるソートアルゴリズム