백준 22988 재활용캠페인 c++ // 투포인터, /2주의사항, 투포예외처리

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

22988번: 재활용 캠페인

1. 의사코드

1. n이 10만 -> 완탐불가 -> 투포?

2. s와 e를 움직이며 관찰한다.

3. e가 이미 x이상인경우-> 가능성없음 -> 제거, cnt+1

4. 병을만들수있으면 만든다. (코드참조)

5. 병을못만드는 경우 -> s+1 -> 더큰값과 합치면 병을 만들수 있는지 탐색한다.

5.1. 위에서 남은 s는 나머지배열에 넣는다.

6. 나머지배열에는 5번조건에따라 nC2해도 병을 못드는 애들만 모여있다.

7. 그런데, 문제에서 x/2는 보장해주니까, 세병을 합치면 병을 만들 수 있다.

8. 정답에 left.size()/3을 더해준다.

 

9. 참고

 

2. /2주의사항

1. x를 2로 나눠야하는상황이다.

2. x가 홀수인경우 짝수인경우 각각 나눠서

mid값을 처리해주자.

3. double 사용은 절대 하지말자! (정확성 보장안됨)

4. 이문제에서는 mid=(x+1)/2로 하면 홀짝인경우 모두 커버가 가능했다. (5인경우 -> 2.5이상 == 3이상 , 6인경우->3이상)

 

3. 투포예외처리

1. s==e인경우,  예외처리를 해주자.

2. 이문제에서는 짞이없고 x미만인 놈이 남아있다. -> 나머지배열로 보낸다.

 

4. 전체코드

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

ll n;
ll m;
vector<ll> v,lef;
int cnt;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n>>m;
	for (int i = 0; i < n; ++i) {
		ll tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	sort(v.begin(), v.end());

	int s = 0, e = n - 1;

	while (s <= e) {
		//이미 x가 된경우 -> 너 가능성없어(더 탐색할필요 없음) -> 제거
		if (v[e] >= m) {
			cnt++;
			e--;
			continue;
		}

		//!!하나만 남은경우 예외처리!!
		//딱 하나만 남았고(짝이없고), x보다 작은경우 쓰레기임
		if (s == e){
			lef.push_back(v[s]);
			break;
		}

		//13(m)통을 만들수있음 -> 만든다
		//이게 최적인 이유 : 가장비싼통입장에서 고를때, 최소값을 고르는게 최적이다.
		// ex) 8의 입장에서는 아무거나골라도 13/2가 넘으므로 최소값(0)을 고르는게 최적임.
		if (v[s] + v[e] >= (m+1)/2) {
			s++;
			e--;
			cnt++;
			continue;
		}
		//두개더해도 13통을 만들수 없는경우
		//세통을 더하면 개손해임
		//작은값을 lef (쓰레기들)배열에 넣고, s를 큰값을 넣으면 되는지 탐색한다.
		if (v[s] + v[e] < (m + 1) / 2) {
			lef.push_back(v[s]);
			s++;
			continue;
		}
	}

	//쓰레기 3개를 모으면 13확정임!
	//두통을합치면 x/2가 보장되기때문에(문제조건)
	cout << cnt + lef.size() / 3;


	

	return 0;
}