読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


SRM 348 Div1 Medium RailwayTickets

問題

(意訳)数直線上に線分が幾つか与えられる。任意の地点で重複する線分はseats以下にしたい。取り除かねばならない線分の最小の数を求めよ。ただし線分の端点は重複と数えない。

問題

線分の右端でソートして貪欲。
ソートした上で数直線上を最初から見ていって、seatsより多く重複する場合には右端がその時点で最も大きい物を取り除くことを繰り返す。

以下ソース。

class RailwayTickets {
public:
  int s2i(string s){
    stringstream ss(s);
    int a; ss >> a; return a;
  }
  int minRejects(vector <string> travel, int seats){
    vector<pair<int, int>> se;
    for(int i = 0; i < (int)travel.size(); i++){
      stringstream ss(travel[i]);
      string s; 
      while(ss >> s){
	int t = s.find('-');
	se.push_back(make_pair(s2i(s.substr(t + 1)), 
			       s2i(s.substr(0, t))));
      }
    }
    sort(ALL(se));
    
    int N = se.size();
    vector<bool> used(N, false);

    for(int i = 0; i < 10000; i++){
      vector<int> idx;
      double p = i + 0.5;
      for(int j = 0; j < N; j++)
	if(!used[j] && se[j].second < p && p < se[j].first) 
	  idx.push_back(j);
      if(idx.size() > seats) //超過している分だけ最も右に伸びているものから取り除く
	for(int k = 0; k < (int)idx.size() - seats; k++)
	  used[idx[idx.size() - 1 - k]] = true;
    }
    return count(ALL(used), true);
  }
};
しょげないでよBaby 眠れば治る