cf 562 div2 C - Increasing by modulo (이분탐색, 그리디)

https://codeforces.com/contest/1169/problem/C

 

<문제설명>

0~m사이 값을 갖는 n개의 요소를 갖는 배열이 주어진다. 임의의 배열 요소을 여러개 골라 (ai+1) % m해주는 것을 하나의 operation이라 할때, 배열 a를 단조증가로 만들기 위해선 최소 몇번의 operation을 해야 하는가?

 

<풀이>

최소 0번 최대 m번의 operation이 필요하다. 어떤횟수 이상의 operation을 수행하면 정렬이되므로 이분탐색.

 

bool pos(k) : k번 operation으로 a 정렬 가능?

 

for(int i=0; i<n; i++) a[i]를 prev로 맞추는 게 가능하다면 prev로 맞추고, 안되면 그냥 두기. (a[i]<prev면 return false)

 

<코드>

int n, m;
vector<int> a;
bool pos(int k) {
	vector<int> b= a;
	
	int p = 0;
	for (int i = 0; i < n; i++) {
		if (p > b[i]) {
			if (p - b[i] > k) return false;
			b[i] = p;
		}
		else {
			if (m - b[i] + p <= k) 
				b[i] = p;
		}
		p = b[i];
	}
	return true;
}

int main() {
	FAST; cin >> n >> m;
	a.resize(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	
	int lo = 0, hi = m;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (pos(mid)) hi = mid;
		else lo = mid + 1;
	}
	cout << lo << '\n';
}