SRM 645 DIV1 Easy - JanuszTheBusinessman

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13603&rd=16277

ホテルに複数の人が宿泊に訪れる。
各ゲストについて到着日と出発日がわかっている。

ここで、ホテルでプロモーションを行うことができ、プロモーションを行うとその日に宿泊している人はよいレビューを残してくれる。

また、プロモーションを受けた人とそうでない人の宿泊日が重なると、プロモーションを受けていない人もよいレビューを残してくれる。

このとき、すべての宿泊客がよいレビューを残してくれる最小のプロモーション開催日数を求める。

解き方


条件を満たす集合の数を求めていけばよい。
プロモーションを「直接」受けている人と宿泊日が重ならなければ
よいレビューを残さないことに注意。

まず、プロモーションの開催日を求める。
このとき、一番早く出発する人からプロモーション日を求めていけば貪欲法で解ける。

プロモーション日が決まったら、そのプロモーションを直接受けられる宿泊客のうち
最も遅く出発する日を求める。

その最も遅い出発日と重なる宿泊客は同じ集合にすることができ、
このオペレーションの回数が最小のプロモーション開催日数となる。

コード


class JanuszTheBusinessman {

public: int makeGuestsReturn(vector<int> arrivals, vector<int> departures) {
int n=arrivals.size();
        int ok[n];
        memset(ok,0,sizeof(ok));

        int ret=0;
        while(true){
        int promday=1e+9;
        FORE(i,0,n)if(!ok[i])promday=min(promday,departures[i]);
        if(promday==1e+9)break;

        int maxcover=promday;
        FORE(i,0,n)if(arrivals[i]<=promday && promday<=departures[i]){
        maxcover=max(maxcover,departures[i]);
        }

        FORE(i,0,n)if(arrivals[i]<=maxcover)ok[i]=1;
        ret++;
        }

        return ret;

}

};

Share this

Related Posts

Previous
Next Post »