(12776) Swap Space

https://www.acmicpc.net/problem/12776

단계별로 풀어보기

42단계(그리디 알고리즘 2) 7번째

 

 

 

a≤b인 드라이브를 초기화한다고 하면, 여유 용량이 a보다 작으면 부족분만큼 추가 드라이브를 구매하고, 포맷한 뒤 b-a만큼 여유 용량이 추가로 생긴다. 임의의 드라이브를 초기화하면 여유 용량이 같거나 커지므로 추가 드라이브 구매를 최소화하기 위해 a가 작은 값부터 포맷해야 한다.

a>b인 드라이브를 초기화한다고 하면, 여유 용량이 a보다 작으면 부족분만큼 추가 드라이브를 구매하고, 포맷한 뒤 a-b만큼 여유 용량이 줄어든다. 임의의 드라이브를 초기화하면 여유 용량이 같거나 작아지므로 추가 드라이브 구매를 최소화하기 위해 a가 큰 값부터 포맷해야 한다.

또한 포맷 후 용량이 늘어나는 드라이브와 줄어드는 드라이브를 비교하면 늘어나는 드라이브를 먼저 해야 이득이다.

이 조건으로 정렬한 뒤 드라이브를 하나씩 탐색하면 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<pair<int,int>> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i].first >> v[i].second;
  
  sort(v.begin(), v.end(), [](auto A, auto B){
    int a= A.second-A.first, b= B.second-B.first;
    
    if(a>=0 && b>=0){
      return A.first < B.first;
    }else if(a<0 && b<0){
      return A.second > B.second;
    }else{
      return a > b;
    }
  });
  
  long ans= 0, rest= 0;
  
  for(auto now:v){
    if(now.first > rest+ans)  ans= now.first-rest;
    
    rest+= now.second-now.first;
  }
  
  cout << ans;
  
  return 0;
}