BOJ 1161 - 버스

BOJ 1161 - 버스

번역이 내용이 누락되어 있어서 그룹끼리 모두 타고 내려야 한다고 생각하고 한시간동안

아니이걸 DP를 안쓰고 어떻게 그리디로 풀지?

이난리하다가 질문 게시판에 오역이 되어있다는 글을 보고 바로 풀 수 있었다.

후 시간 개아깝네

문제는 오래된 문제답게 단순한데, 그냥 $S_i$ 로 정렬을 하고 최대, 최소값을 관리할 수 있는 multiset 같은걸로 승객이 내리는 시간을 관리한다.

$S_i$ 로 정렬되어 있으므로 현재 $S_i$ 보다 이전에 내린 승객들을 모두 빼주고,

만약 버스가 비어있으면 넣을 수 있는데까지 넣고,

비어있지 않다면 버스의 내리는 시간의 최대값이 더 줄어들 수 있을 때 까지 현재 승객들을 태운다.

void solve() {  
   int K, N, C;  
   cin >> K >> N >> C;  
   vector<array<int, 3>> a(K);  
   for (auto &[s, e, m]: a) cin >> s >> e >> m;  
   sort(all(a), [&](auto &a, auto &b) {  
      if (a[0] == b[0])return a[1] < b[1];  
      return a[0] < b[0];  
   });  
   int s, e, m, ans = 0;  
   multiset<int> ride_off;  
   for (auto cur: a) {  
      s = cur[0], e = cur[1], m = cur[2];  
      while (sz(ride_off) && *ride_off.begin() <= s)  
         ride_off.erase(ride_off.begin());  
      while (m && sz(ride_off) < C) {  
         ride_off.insert(e);  
         ans++;  
         m--;  
      }  
      while (m && sz(ride_off) && *ride_off.rbegin() > e) {  
         ride_off.erase(ride_off.find(*ride_off.rbegin()));  
         ride_off.insert(e);  
         m--;  
      }  
   }  
   cout << ans;  
}